代码随想录：279. 完全平方数
279. 完全平方数
这道题与322比较像只是需要先预处理一下，后续完全背包dp依然采用滚动数组优化
class Solution {
public:
int numSquares(int n) {
int a[105];//预处理完全平方数
memset(a, 1, sizeof(a)); //赋较大的初始值
for (int i = 1; i <= 100; i++) {
a[i] = i * i; //存平方数
}
vector<int> dp(n + 5, INT_MAX);
dp[0] = 0; //没有就是0
for (int i = 1; a[i] <= n; i++) {
//前i个平方数
for (int j = a[i]; j <= n; j++) {
//滚动数组优化，取最小值加1
if (dp[j - a[i]] != INT_MAX)
dp[j] = min(dp[j], dp[j - a[i]] + 1);
}
}
return dp[n];//一定能找到
}
};