力扣算法篇：完全平方数(dp)

动态规划五部曲： 1、确定dp数组及其下标含义 dp[j]:和为j的组成和的最少完全平方数个数 2、确定递推式

dp[j] = min(dp[j-i^2]+1,dp[j]);

3、初始化 dp[0] = 0;非零下标数组值为最大 4、确定遍历顺序 从前往后 5、举例推导dp

dp数组变化：
0 1 2 3 4 5 
0 1 2 3 1 2 
0 1 2 3 1 2

题解：

class Solution {
          
   
public:
    int numSquares(int n) {
          
   
        //dp[j]:和为j的组成和的最少完全平方数个数
        //完全背包
        //递推式：dp[j] = min(dp[j-i^2]+1,dp[j]);
        //定义vector
        vector<int> dp(n+1,INT_MAX);
        dp[0] = 0;
        //计算dp
        for(int i = 1;i<=int(sqrt(n))+1;i++){
          
   
            for(int j = i*i;j<=n;j++){
          
   
                if(dp[j-i*i]!=INT_MAX){
          
   
                    dp[j]=min(dp[j-i*i]+1,dp[j]);
                }
            }
            //shuchu
            // for(int x = 0;x<=n;x++){
          
   
            //     cout<<dp[x]<<" ";
            // }
            // cout<<endl;
        }
        return dp[n];
    }
};