原题链接
题意：
给一个非整数，算出其最少可以由几个完全平方数组成（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]; } };
转载于:https://www.cnblogs.com/ruoh3kou/p/9914291.html
