[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];
  }
};