LeetCode 279. 完全平方数

题目描述链接：https://leetcode-cn.com/problems/perfect-squares/

解题思路：动态规划。参考题解，基本的动态转移方程可以表示为dp[i]=min(dp[i-j]+1) 其中j为完全平方数，

所以我们找到1至n的完全平方数然后1 到n 求出全部dp[i]，最后dp[n]即为答案。

如此解题过程如下：

（1）状态标识 dp[i]标识数字i用完全平方数表示的方案数

（2）边界确定  dp[0]=0

（3）状态转移方程 dp[i]=min(dp[i-j]+j)+1其中j为小于i的完全平方数

最后由此易得LeetCode C++解题代码如下：

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

其时间复杂度为O(n*n^1/2)    空间复杂度O(n)。