本文主要是介绍代码随想录第45天 | 70. 爬楼梯 （进阶） 、 322. 零钱兑换 、 279.完全平方数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、前言：
参考文献：代码随想录
今天的主题是完全背包，要牢记完全背包和01背包的区别；一个是物品无限次使用，另一个是物品只能使用一次；
二、爬楼梯（进阶）
1、思路：
这一个题目首先要弄清楚谁是背包，谁是物品，我一开始就弄反了，结果就出错了，还有递推公式是怎么来的。
继续动态规划五部曲：
前提n为楼梯阶数，m为爬楼梯的能力，一次最多怕几阶层
（1）dp数组：
vector<int> dp (n + 1, 0);采用的还是一维递推数组，下标代表阶梯的位置，数值代表到该阶梯的方式数量。
n为楼梯的结束，默认初始化为0，这里就是一个思想，楼梯为阶数为背包的容量；
解释：
因为楼梯的阶数是固定的，而步数是变化的；
（2）初始化：
dp[0] = 1;这里可以这么解释，当楼梯阶数为0时，就只有一种方法爬楼梯——不爬；
（3）递推公式：
if (i - j >= 0) {dp[i] += dp[i - j];}又是一个小细节和难点，先说内部递推公式，里面就是从第i个阶梯下有多少种方法，再加上i-j的阶梯处有几种方法。外部条件是i - j说明要背包容量大于物品大小时才能进行递推公式；
（4）遍历顺序：
for (int i = 1; i <= n; i++) {// 再遍历物品for (int j = 1; j <= m; j++) {if (i - j >= 0) {dp[i] += dp[i - j];}}}先便利的背包，再遍历的物品，就是排列问题，每一种走的方式都不一样；
2、整体代码如下：
#include<iostream>
#include<vector>
using namespace std;int main() {int n; // 楼梯阶数，类似于背包容量int m; // 爬的能力大小,类似于物品cin >> n >> m;// 1、定义dp数组vector<int> dp (n + 1, 0);// 2、初始化dp[0] = 1; // 阶梯为0，能力为任何时种数都为1种// 3、遍历顺序// 先便利背包容量for (int i = 1; i <= n; i++) {// 再遍历物品for (int j = 1; j <= m; j++) {if (i - j >= 0) {dp[i] += dp[i - j];}}}// 5、打印dp数组for (auto i : dp) {cout << i << endl; }cout << dp[n] << endl;return 0;
}三、零钱兑换
1、思路：
现在做dp总是感觉有感觉，但是做不出来。。
这个题目的主要思路首先要确定一个思想：我们需要最少的硬币来组成我的面额；
（1）确定dp数组：
vector<int> dp(amount + 1, INT_MAX);这个dp数组表示的是在所需面额为j的情况下，组成该面额的硬币最小数为dp[j]；
amount是需要的零钱数，然后全部初始化为INT_MAX，为之后寻找最小值做准备；
（2）确定递推公式：
dp[j] = min(dp[j ], dp[j - coins[i]] + 1);
是为了寻找最小的硬币组成大小，通过原数组和加上该硬币下的dp数组进行比较；
（3）初始化：
dp[0] = 0;因为当面额为0时的题目要求是种类为0；
（4）遍历顺序：
for (int i = 0; i < coins.size(); i++) {for (int j = coins[i]; j <= amount; j++) {// 判断需要递推的dp数组是否还未被使用；if (dp[j - coins[i]] != INT_MAX) {// 4、寻找最小的硬币数字dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}}这是先遍历种类，再遍历背包，注意这里是从小到大遍历背包，说明可以重复的利用硬币；
2、整体代码如下：
class Solution {
public:int coinChange(vector<int>& coins, int amount) {// 1、定义dp数组vector<int> dp(amount + 1, INT_MAX);// 2、初始化dp[0] = 0;// 3、先遍历物品，再遍历背包for (int i = 0; i < coins.size(); i++) {for (int j = coins[i]; j <= amount; j++) {// 判断需要递推的dp数组是否还未被使用；if (dp[j - coins[i]] != INT_MAX) {// 4、寻找最小的硬币数字dp[j] = min(dp[j], dp[j - coins[i]] + 1);}}}// 5、打印dp数组// for (auto i : dp) {// cout << i << endl;// }return dp[amount] == INT_MAX ? -1 : dp[amount];}
};四、完全平方数
1、思路：
本题322硬币题目类似，唯一的区别就是需要创建一个的平方数组数组即可；
2、整体代码如下：
class Solution {
public:int numSquares(int n) {// 与322硬币最小数类似；// 创建种类vector<int> nums(100, 0);for (int i = 1; i <= 100; i++) {nums[i - 1] = i * i;}// 1、创建dp数组vector<int> dp(n + 1, INT_MAX);// 2、初始化dp[0] = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] > n) {break;}for (int j = nums[i]; j <= n; j++) {if (dp[j - nums[i]] != INT_MAX) {dp[j] = min(dp[j], dp[j - nums[i]] + 1);}}}return dp[n] == INT_MAX ? -1 : dp[n];}
};Time Study Today: 1h
leave message:
From hill to hill no bird in flight; from path to path no man in sight.
千山鸟飞绝，万径人踪灭。
这篇关于代码随想录第45天 | 70. 爬楼梯 （进阶） 、 322. 零钱兑换 、 279.完全平方数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
