力扣题解（完全平方数）

279. 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

思路：

可以看成在所有满足（k*k<=n,k>=1）的所有k所组成的数组中取某些数，可以多次取同一个数，然后和为n的最小组合数，因此和零钱兑换问题实质上一样。

dp[i][j]表示前i个数，和为j的最小数量。

dp[i][j]=min(dp[i-1][j],dp[i][j-num[i]]+1)。

初始化：

i为0，j除了为0均不可能实现，因此设为一个很大的数。

j为0，对任意i，都有零个数字组成j的可能，因此dp[i][0]=0;

class Solution {
public:
 int coinChange(vector<int>& coins, int amount) {
     int n=coins.size();
     int INF=0x3f3f3f3f;
     vector<vector<int>>dp(n+1,vector<int>(amount+1,INF));
     for(int i=0;i<=n;i++)
     {
        dp[i][0]=0;
     }
     coins.insert(coins.begin(),0);
     for(int i=1;i<=n;i++)
     {
        for(int j=1;j<=amount;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j-coins[i]>=0&&dp[i][j-coins[i]]!=-1)
            {
              //  cout<<i<<j-coins[i]<<" ||";
        
            dp[i][j]=min(dp[i][j],dp[i][j-coins[i]]+1);
            
            }
        }
     }
     return dp[n][amount]==INF?-1:dp[n][amount];


    }
    int numSquares(int n) {
      vector<int>coins;
      int i=1;
      while(i*i<=n)
      {
        coins.push_back(i*i);
        i++;
      }
     if((i-1)*(i-1)==n)
     return 1;
      return coinChange(coins,n);
    }
};