动态规划----完全平方数（3种写法，逐步简化）

题目链接：完全平方数

完全平方数可以认为是完全背包问题。每一个平方小于n的平方数都是物品，而完全平方数之和n就是背包容量。每一个平方和都可以无限次使用。

写法1：把所有小于n的平方数存入数组nums,使用二维dp数组。

递推公式的推导可以看完全平方数

   int numSquares(int n) {int num = (int)sqrt(n);vector<int> nums(num, 0);//for(int i = 0; i<nums.size(); i++){nums[i] = (i+1)*(i+1);}vector<vector<int>> dp(nums.size(), vector<int>(n+1, 0));//初始化第一列for(int i = 0; i<nums.size(); i++){dp[i][0] = 0;}//初始化第一行for(int i=0; i<=n; i++){dp[0][i] = i;}for(int i=1; i<nums.size(); i++){for(int j=1; j<=n; j++){if(j-nums[i]>=0)dp[i][j] = min(dp[i-1][j], dp[i][j-nums[i]]+1);elsedp[i][j] = dp[i-1][j];}}return dp[nums.size()-1][n];}

写法2：把所有小于n的平方数存入数组nums,使用一维dp数组。

int numSquares(int n) {int num = (int)sqrt(n);vector<int> nums(num, 0);for(int i = 0; i<nums.size(); i++){nums[i] = (i+1)*(i+1);}vector<int> dp(n+1, 0);for(int i=0; i<=n; i++){dp[i] = i;}for(int i=1; i<nums.size(); i++){for(int j=1; j<=n; j++){if(j-nums[i]>=0)dp[j] = min(dp[j], dp[j-nums[i]]+1);}}return dp[n];}

写法三、不用nums数组，先遍历背包，再遍历物品。因为：

dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。
此时我们要在所有满足i*i<j的i中选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);

int numSquares(int n) {vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 0; i <= n; i++) { // 遍历背包for (int j = 1; j * j <= i; j++) { // 遍历物品dp[i] = min(dp[i - j * j] + 1, dp[i]);}}return dp[n];}