力扣 -- 279. 完全平方数（完全背包问题）

解题步骤：

参考代码：

未优化代码：

class Solution {
public:int numSquares(int n) {const int INF=0x3f3f3f3f;int m=sqrt(n);//多开一行，多开一列vector<vector<int>> dp(m+1,vector<int>(n+1));//初始化第一行dp[0][0]=0;for(int j=1;j<=n;j++){dp[0][j]=INF;}//第一列不需要初始化//填表for(int i=1;i<=m;i++){//记得从0开始，因为第一列没有初始化for(int j=0;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);}}}//返回值，m就是根号nreturn dp[m][n];}
};

优化后的代码：

class Solution {
public:int numSquares(int n) {const int INF=0x3f3f3f3f;int m=sqrt(n);//多开一行，多开一列,初始化vector<int> dp(n+1,INF);dp[0]=0;//填表for(int i=1;i<=m;i++){//记得从0开始，因为第一列没有初始化for(int j=i*i;j<=n;j++){//状态转移方程dp[j]=min(dp[j],dp[j-i*i]+1);}}return dp[n];}
};

你学会了吗？？？