代码随想录打卡—day45—【DP】— 8.29 完全背包应用

1 70. 爬楼梯（完全背包版）

70. 爬楼梯

完全背包+装满的选法+排列的套路，AC代码：

class Solution {
public:/*完全背包的思路:1 2是两个物体 可以无限取*/int dp[50]; // 能爬到第i楼的选法的排列数/*dp[j] += dp[j - i];dp[0] = 1for容积j++ for物体i++  排列+无限个模拟——n=3*/int climbStairs(int n) {dp[0] = 1;for(int j = 0; j <= n; j++)for(int i = 1; i <= 2; i++) //物体if(j >= i)dp[j] += dp[j - i];// for(int i = 1; i <= 2; i++)// {//      for(int j = 0; j <= n; j++)//         cout << tmp[i][j] << ' ';//     puts("");// }return dp[n];}
};

2 322. 零钱兑换

322. 零钱兑换

之前做过，直接看这篇

3 279. 完全平方数

279. 完全平方数

之前没学多重背包之前看到题目是蒙的，现在学完时候很自然就做出来了，AC代码：

class Solution {
public:int dp[10010];  // dp[1]表示 凑成i的完全平方数最少需要的数目/*转成完全背包物品：i = 1....sqrt(n)背包：ndp[j] = min(dp[j- i]+1,dp[j])装i   不撞idp[0] = 0 其他非0下标全设为INT_MAXi++j++模拟——*/int numSquares(int n) {dp[0] = 0;for(int j = 1; j <= n; j++)dp[j] = INT_MAX;for(int i = 1; i*i <= n; i++){for(int j = 0; j <= n; j++){if(j >= i*i)dp[j] = min(dp[j- i*i]+1,dp[j]);else dp[j] = dp[j];}// for(int j = 0; j <= n; j++) cout << dp[j] << ' ';// puts("");}return dp[n];}
};