Leetcode.279.Perfect Squares

题目

找到一个数最少由多少个完美数组成。完美数：n²。

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9

思路

要么递归，要么DP。明显DP是一个不错的选择。
dp[i] = min(dp[i], dp[i-j*j]+1);

int numSquares(int n) {
    vector<int> dp(n+1, INT_MAX);
    dp[0] = 0;
    for (int i = 1;i <= n; i++) {
        int a = sqrt(i);
        for (int j = 1; j <= a; j++) {
            dp[i] = min(dp[i], dp[i-j*j]+1);
        }
    }
    return dp[n];
}

总结

熟练掌握DP，DP关键是理解其中对应的数学公式。