完美平方数都可以看做一个普通数加上一个完美平方数
如图所示，红色部分表示平方数，所有的完美平方数都可以看做一个普通数加上一个完美平方数，那么递推式就变为了：dp[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j])。
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
for(int i = 1; i<=n ;i++){
dp[i] = i; // 最多都由1组成
for(int j = 1; j*j<=i; j++){
dp[i] = Math.min(dp[i], dp[i-j*j]+1);
}
}
return dp[n];
}
}
279. Perfect Squares 如图所示，红色部分表示平方数，所有的完美平方数都可以看做一个普通数加上一...
有点类似 perfect squares那道题-279.
LeetCode 279. Perfect Squares Description Given a positiv...
279. Perfect Squares（Medium) Given a positive integer n, ...
原题：279. Perfect Squares Given a positive integer n, find ...
279. Perfect Squares image.png参考： https://www.geeksforgee...
0X00 leetcode 做了 4 道 leetcode 279. Perfect Squares leetco...
278. First Bad Version 二分查找的思路 279. Perfect Squares 使用动态规...
https://leetcode.com/problems/perfect-squares/description...
第一种做法是动态规划，用一个数组perfect[i]来记录到perfect[i]数目，perfect[0]=0，对...
本文标题：[DP]279. Perfect Squares
本文链接：https://www.haomeiwen.com/subject/kyhwfftx.html
网友评论