[LeetCode] Perfect Squares 完全平方数
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Example 1:
Input: n =12Output: 3 Explanation:12 = 4 + 4 + 4.
Example 2:
Input: n =13Output: 2 Explanation:13 = 4 + 9.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
远古解法 有空再看
class Solution {public int numSquares(int n) {List squares = generateSquares(n);Queue queue = new LinkedList<>();boolean[] marked = new boolean[n+1];queue.add(n);marked[n] = true;int level = 0;while(!queue.isEmpty()){int size = queue.size();level++;while(size-- > 0){int cur = queue.poll();for(int s : squares){int next = cur - s;if(next < 0)break;if(next == 0)return level;if(marked[next])continue;marked[next] = true;queue.add(next);}}}return n;}/*** 生成小于 n 的平方数序列* @return 1,4,9,...*/private List generateSquares(int n){List squares = new ArrayList<>();int square = 1;int diff = 3; //1 4 9 16 25while(square <= n){//差值 3 5 7 9 11squares.add(square);square += diff;diff += 2;}return squares;}}
这种解法跟上面有些不同,上面那种解法是初始化了整个长度为n+1的dp数字,但是初始化的顺序不定的,而这个种方法只初始化了第一个值为0,那么在循环里计算,每次增加一个dp数组的长度,里面那个for循环一次循环结束就算好下一个数由几个完全平方数组成,直到增加到第n+1个,返回即可,想更直观的看这两种DP方法的区别,建议每次循环后都打印出dp数字的值来观察其更新的顺序,参见代码如下:
class Solution {public int numSquares(int n) {List squareList = generateSquareList(n);int[] dp = new int[n + 1];for(int i=1; i <=n; i++){int min = Integer.MAX_VALUE;for(int square : squareList){if(square > i)break;//按爬梯子来理解 每个square 与 i- square的差值 都能组成i 也就是i-square的个数再加上square的个数 也就是dp[i -square] + 1min = Math.min(min, dp[i - square] + 1);}dp[i] = min;}return dp[n]; }private List generateSquareList(int n) {List squareList = new ArrayList<>();int diff = 3;int square = 1;while (square <= n) {squareList.add(square);square += diff;diff += 2;}return squareList;}
}
这道题远不止这一种解法,我们还可以用动态规划Dynamic Programming来做,我们建立一个长度为n+1的一维dp数组,将第一个值初始化为0,其余值都初始化为INT_MAX, i从0循环到n,j从1循环到i+j*j <= n的位置,然后每次更新dp[i+j*j]的值,动态更新dp数组,其中dp[i]表示正整数i能少能由多个完全平方数组成,那么我们求n,就是返回dp[n]即可,也就是dp数组的最后一个数字。需要注意的是这里的写法,i必须从0开始,j必须从1开始,因为我们的初衷是想用 dp[i] 来更新 dp[i + j * j],如果 i=0, j=1 了,那么 dp[i] 和 dp[i + j * j] 就相等了,怎么能用本身dp值加1来更新自身呢,参见代码如下:
class Solution {
public:int numSquares(int n) {vector dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 0; i <= n; ++i) {for (int j = 1; i + j * j <= n; ++j) {dp[i + j * j] = min(dp[i + j * j], dp[i] + 1);}}return dp.back();}
};










