[leetcode] #279 Perfect Squares (medium)

原题链接

题意：

给一个非整数，算出其最少可以由几个完全平方数组成（1，4，9，16……）

思路：

可以得到一个状态转移方程

dp[i] = min(dp[i], dp[i - j * j] + 1);

代码如下：

Runtime: 60 ms, faster than 69.83% 有点慢

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