代码随想录第45天 | 70. 爬楼梯 （进阶） 、 322. 零钱兑换 、 279.完全平方数

本文主要是介绍代码随想录第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.完全平方数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---