【Day50】代码随想录之动态规划完全背包_70. 爬楼梯进阶_322. 零钱兑换

【Day50】代码随想录之动态规划完全背包_70. 爬楼梯进阶_322. 零钱兑换 _279.完全平方数

本文主要是介绍【Day50】代码随想录之动态规划完全背包_70. 爬楼梯进阶_322. 零钱兑换 _279.完全平方数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- - 动态规划理论基础
  - - 动规五部曲：
    - 出现结果不正确：
  - 70. 爬楼梯进阶
  - 322. 零钱兑换
  - 279.完全平方数

动态规划理论基础

动规五部曲：

确定dp数组下标及dp[i] 的含义。
递推公式：比如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。
初始化dp数组。
确定遍历顺序：从前到后or其他。
打印。

出现结果不正确：

打印dp日志和自己想的一样：递推公式、初始化或者遍历顺序出错。
打印dp日志和自己想的不一样：代码实现细节出现问题。

70. 爬楼梯进阶

参考文档：代码随想录

分析：
根据题目描述是完全背包的排列问题，遍历顺序为先背包再物品。
dp五部曲：

dp[i]含义：爬到j楼的方法个数。
递推公式：dp[i] += dp[i-j];
初始化：dp[0] = 1, 其余位置为0。
遍历顺序：先背包再物品。

代码：

#include<iostream>
#include<stdio.h>
#include<vector>using namespace std;int main(){int m = 0, n = 0;scanf("%d%d",&n, &m);vector<int> dp(n+1, 0);dp[0] = 1;for(int i = 1; i <= n; i++){//先背包for(int j = 1; j <= m; j++){//再物品if(i >= j) dp[i] += dp[i-j];}}printf("%d", dp[n]);return 0;
}

322. 零钱兑换

参考文档：代码随想录

分析：
dp公式：dp[j] = min(dp[j], dp[j-coins[i]]+1)。
因为题目求的是最少的硬币个数，所以排列组合都可以，即物品和背包的遍历顺序均可。
初始化需要注意dp[0]是0，其余的为了不影响之后的取最小值，定义为32位数的最大值INT_MAX。

代码：

class Solution {
public:int coinChange(vector<int>& coins, int amount) {//dp[j]:amount=j需要的最少硬币个数//dp[j] = min(dp[j], dp[j-coins[i]]+1);//dp[0] = 0, 其他初始化INT_MAXvector<double> dp(amount+1, INT_MAX);dp[0] = 0;for(int i = 0; i < coins.size(); i++){for(int j = coins[i]; j <= amount; j++){dp[j] = min(dp[j], dp[j-coins[i]]+1);}}if(dp[amount] == INT_MAX) return -1;return dp[amount];}
};

279.完全平方数

参考文档：代码随想录

分析：
dp公式改变：dp[j] = min(dp[j], dp[j-i*i]+1);

代码：

class Solution {
public:int numSquares(int n) {//dp[j]: 和为j的完全平方数的最少数量//dp[j] = min(dp[j], dp[j-i*i]+1);//初始化：dp[0] = 0，其余初始化是INT_MAXint nums = n/2;if(n == 1) nums = 1;vector<double> dp(n+1, INT_MAX);dp[0] = 0;for(int i = 1; i <= nums; i++){for(int j = i*i; j <= n; j++){dp[j] = min(dp[j], dp[j-i*i]+1);}}return dp[n];}
};