Leetcode 279. 完全平方数

题目描述：

https://leetcode-cn.com/problems/perfect-squares/

解题思路：

同样是dp，一开始的想法是，对于每个数i做拆分为j和(i-j)，利用动态转移方程dp[i]=min(dp[i], dp[j]+dp[i-j])。由于对于一个整数的拆分是从1到i/2的次数，n的数字很大，所以超时。

进一步考虑，其实不用考虑每一种拆分情况，只需要考虑min(dp[i], dp[i-j*j])，这里j的取值范围就为j*j<=i，这样就只需要对每个平方数的跨度去求一次。

代码：

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