leetcode-279. Perfect Squares 完全平方數

Given a positive integer n, find the least number of perfect square numbers (for example,  1, 4, 9, 16, ... ) which sum to n. Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.

給定正整數 n，找到若幹個完全平方數（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數的個數最少。 示例 1: 輸入: n = 12 輸出: 3  解釋: 12 = 4 + 4 + 4. 示例 2: 輸入: n = 13 輸出: 2 解釋: 13 = 4 + 9. 在真實的面試中遇到過這道題？

思路：建一個n+1長度的dp數組，将第一個值初始化為0，其餘值都初始化為INT_MAX，i從0循環到n，j從1循環到i+j*j<=n的位置，然後每次更新dp[i+j*j]的值，動态更新dp數組，dp[i]表示正整數i至少能由多少個完全平方數組成，那也就是求n，最終傳回dp[n]即可。 

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1 ,INT_MAX);
        dp[0]= 0;
        for(int i=0;i<=n;++i)
        {
            for(int j=1;i+j*j<=n;++j)
                dp[i+j*j]=min(dp[i+j*j],dp[i]+1);
        }
        return dp.back();
    }
};