1.题目解析

题目来源

279.完全平方数——力扣

测试用例 

2.算法原理

1.状态表示

完全背包问题通常都是使用一个二维数组来表示其状态，这里是

dp[i][j]：在[1,i]区间选择平方数，当此时已选择平方数的总和完全等于j时所选择的最小平方数个数

2.状态转移方程

3.初始化

4.填表顺序

从上到下，每一行从左到右

5.返回值 

这里最终返回dp[+1][n]这个位置即可，因为不可能选择到n^2这个位置的平方数

3.实战代码

class Solution {
public:int numSquares(int n) {int m = sqrt(n);vector<vector<int>> dp(m+1,vector<int>(n+1));for(int j = 1;j <= n;j++){dp[0][j] = 0x3f3f3f3f;}    for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++){dp[i][j] = dp[i-1][j];if(j >= i*i){dp[i][j] = min(dp[i][j],dp[i][j-i*i] + 1);}}}return dp[m][n];}
};

代码解析