LeetCode刷题实战279:完全平方数
示例
示例 1:
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4
示例 2:
输入:n = 13
输出:2
解释:13 = 4 + 9
解题
class Solution {
public int numSquares(int n) {
// 动态规划
int[] dp = new int[n+1];// 默认初始化值都为0
for(int i=1;i<=n;i++) {
// 最坏的情况就是每次都为1相加
dp[i] = i;
// 对其更新
for(int j=1;i-j*j>=0;j++) {
dp[i] = Math.min(dp[i],dp[i-j*j]+1);//动态转移方程
}
}
return dp[n];
}
}
赞 (0)