https://leetcode.com/problems/perfect-squares/description/
解题思路:
- 两个循环:核心是i + j * j <= n, 对dp[i + j * j]进行更新
代码:
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 = 0; i <= n; i++){
for(int j = 1; i + j * j <= n; j++){
dp[i+j*j] = Math.min(dp[i+j*j], dp[i] +1);
}
}
return dp[n];
}
}
网友评论