代码随想录：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; //没有就是0for (int i = 1; a[i] <= n; i++) {//前i个平方数for (int j = a[i]; j <= n; j++) {//滚动数组优化，取最小值加1if (dp[j - a[i]] != INT_MAX)dp[j] = min(dp[j], dp[j - a[i]] + 1);}}return dp[n];//一定能找到}
};