LeetCode_279. 完全平方數

題目描述：

給定正整數 n，找到若幹個完全平方數（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數的個數最少。

示例 1:

輸入: n = 12
輸出: 3 
解釋: 12 = 4 + 4 + 4.
示例 2:

輸入: n = 13
輸出: 2
解釋: 13 = 4 + 9.      

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,0);//dp[i]表示組成正整數i的最少完全平方數的個數，初始化為0
        if(n==0)
            return 0;
        for(int i=1;i<=n;i++){//正整數從1到n的所有最小個數都可以求出
            dp[i]=i;//初始化成最大個數,即i=1+1+...+1,i個1相加
            for(int j=1;pow(j,2)<=i;j++){//周遊所有滿足條件的完全平方數
                dp[i]=min(dp[i],dp[i-pow(j,2)]+1);//此處一定要從最小的完全平方數開始
            }
        }
        return dp[n];
    }
};