最全微信小程序名单_网站外链建设可以提升网站权重吗_曼联对利物浦新闻_b站推广渠道

思路

1. dp数组定义：和为 j 的完全平方数的最少数量
2. 递推公式：dp[j] = min(dp[j], dp[j-nums[i]] + 1 );
3. dp数组初始化：dp[0] = 0;
4. 遍历顺序：不涉及组合排列，先物品先背包都可，由于是完全背包所以第二层是顺序
5. 时间复杂度：     

代码

class Solution {
public:int numSquares(int n) {vector<int> nums;for(int i = 1; i <= 1000; i++){if(i*i > n){break;}nums.push_back(i*i);}vector<int> dp(n+1, INT_MAX);int m = nums.size();dp[0] = 0;for(int i = 0; i < m;i++){for(int j = 0; j <= n;j++){if(j >= nums[i]){dp[j] = min(dp[j], dp[j-nums[i]] + 1 );}}}return dp[n];}
};