题目来源
一道DP题，求一个数最少由几个平方数组成。我一开始用二维DP，
因为是个完全背包问题，所以需要注意每个数都是可以取多次的。
代码如下：
class Solution {
public:
int numSquares(int n) {
int l = sqrt(n);
vector<int> squares(l+1);
vector<vector<int>> dp(l+1, vector<int>(n+1, 0));
for (int i=1; i<=l; i++) {
squares[i] = i * i;
}
for (int i=1; i<=n; i++)
dp[1][i] = i;
for (int i=2; i<=l; i++)
for (int j=1; j<=n; j++) {
if (j >= squares[i])
dp[i][j] = min(dp[i-1][j], min(dp[i-1][j-squares[i]] + 1, dp[i][j-squares[i]] + 1));
else
dp[i][j] = dp[i-1][j];
}
return dp[l][n];
}
};
但是内存溢出了，所以需要改成一维DP。
代码如下：
class Solution {
public:
int numSquares(int n) {
int l = sqrt(n);
vector<int> squares(l+1);
vector<int> dp(n+1, 0);
for (int i=1; i<=l; i++) {
squares[i] = i * i;
}
for (int i=1; i<=n; i++)
dp[i] = i;
for (int i=1; i<=n; i++) {
for (int j=1; j<=l && squares[j] <= i; j++)
dp[i] = min(dp[i], dp[i-squares[j]] + 1);
}
return dp[n];
}
};
然后看了讨论区，发现了静态DP，时间瞬间降了好多，感觉很厉害的样子！
代码如下：
class Solution {
public:
int numSquares(int n) {
static vector<int> dp{0};
while (dp.size() <= n) {
int m = dp.size(), squares = INT_MAX;
for (int i=1; i*i<=m; i++)
squares = min(squares, dp[m-i*i] + 1);
dp.push_back(squares);
}
return dp[n];
}
};
