概述
https://leetcode.com/problems/perfect-squares/
贪心貌似不行欸。
二维动态规划
TLE 了。
class Solution {
public:
vector<vector<int>> dp;
int numSquares(int n) {
dp.resize(n + 1, vector<int>(sqrt(n) + 1, -1));
return helper(n, sqrt(n));
}
int helper(int n, int s) {
if (n == 0) return 0;
if (s == 1) return n;
if (dp[n][s] != -1) return dp[n][s];
dp[n][s] = INT_MAX;
for (int i = 0; i * s * s <= n; i ++) {
dp[n][s] = min(dp[n][s], i + helper(n - i * s * s, s - 1));
}
return dp[n][s];
}
};
一维的动态规划
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1, INT_MAX);
dp[0] = 0;
for (int i = 0; i <= n; i ++) {
for (int j = 1; j * j <= i; j ++) {
dp[i] = min(dp[i], 1 + dp[i - j * j]);
}
}
return dp[n];
}
};
上面可以再优化一下，因为测试时是多个 case，当已经计算过的就不必再计算了，具体实现见： https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics)
why Static Dynamic Programming is faster than Dynamic Programming
it's faster because an answer once calculated for a test case remains for the upcoming test case say you calculated for 100 and the next test case is for 50 so you have already calculated it. static members once created remain for the lifetime of the program.