dp[i] = min( min_prev, dp[ i - j*j ] + 1 );
j starts from 1, 2, 3...
update every iteration j++.
public class Solution {
public int numSquares(int n) {
int dp[] = new int[n+1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i=1; i<=n; i++) {
int min_cnt = Integer.MAX_VALUE;
int j=1;
while(i - j*j >= 0) {
min_cnt = Math.min(min_cnt, dp[i-j*j]+1);
j++;
}
dp[i] = min_cnt;
}
return dp[n];
}
}
网友评论