最少完全平方数个数[动态规划]

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

思考：
// 分析：定义dp[i]表示数字i由完全平方数组成的最少个数；
// 1、如果i恰好为一个完全平方数，则dp[i] = 1;
// 2、如果i不能恰好表示为一个完全平方数，dp[i] = dp[i-sqrt(i)sqrt(i)] + 1;
// 所以状态转移为: dp[i] = min(dp[i], dp[i - sqrt(i)sqrt(i)] + 1);

int numSquares(int n) {
    int sqrt_n = (int)sqrt(n);
    vector<int> dp(n+1);
    // initialize status
    // 状态初始化：dp[i] = i表示最差情况：每一个数都是最大个数的完全平方数1组成；
    for(int i = 0; i <= n; ++i)
        dp[i] = i;
    // 从小到大的遍历，获取每一个i的最小完全数和个数
    for(int i = 1; i <= n; ++i)
    {
        // 状态转移计算dp[i]的最小完全数和的个数
        for(int j = 1; j*j <= i; ++j)
            dp[i] = min(dp[i], dp[i-j*j] + 1);
    }
    return dp[n];
}

欢迎交流，批评指正！