【hot100-java】【完全平方数】
R8-dp篇
深夜更新，时间甚紧。
目录
记忆化
递推式
ps：
从记忆化到递推
记忆化
class Solution {private static final int[][] memo = new int[101][10001];static{for (int [] row:memo){Arrays.fill(row,-1);//-1表示没有计算过}}private static int dfs(int i,int j){if(i==0){return j==0?0:Integer.MAX_VALUE;}//计算过if (memo[i][j]!=-1){return memo[i][j];}//只能不选if (j<i*i){return memo[i][j]=dfs(i-1,j);}//不选或者选return memo[i][j]=Math.min(dfs(i-1,j),dfs(i,j-i*i)+1);}public int numSquares(int n) {return dfs((int) Math.sqrt(n),n);}
}
递推式
class Solution {private static final int N=10000;private static final int[][] f=new int[101][N+1];static{Arrays.fill(f[0],Integer.MAX_VALUE);f[0][0]=0;for (int i=1;i*i<=N;i++){for (int j=0;j<=N;j++){if(j<i*i){//只能不选的情况f[i][j]=f[i-1][j];}else{f[i][j]=Math.min(f[i-1][j],f[i][j-i*i]+1);}}}}public int numSquares(int n) {//也可以写f[100][n]return f[(int) Math.sqrt(n)][n];}
}
ps：
java语法
Arrays.fill(f[0], Integer.MAX_VALUE);