网站建设与开发课程内容,做的网站怎么打开是白板,东莞网站设计公司哪家好,电商好做吗现在文章目录 70.爬楼梯#xff08;进阶版#xff09;⭐️322. 零钱兑换思路CPP代码总结 279.完全平方数思路CPP代码 70.爬楼梯#xff08;进阶版#xff09; 卡码网#xff1a;57. 爬楼梯 文章讲解#xff1a;70.爬楼梯(进阶版) 本题就是典型了完全背包排列问题#xff0c;… 文章目录 70.爬楼梯进阶版⭐️322. 零钱兑换思路CPP代码总结 279.完全平方数思路CPP代码 70.爬楼梯进阶版 卡码网57. 爬楼梯 文章讲解70.爬楼梯(进阶版) 本题就是典型了完全背包排列问题也没有什么绕弯比较简单 #include bits/stdc.h
using namespace std;int main () {int m, n;cin n m;std::vectorint dp(n 1, 0);dp[0] 1;for (int j 1; j n; j) {for (int i 0; i m; i) {if (j i)dp[j] dp[j - i]; }}cout dp[n] endl;return 0;
}⭐️322. 零钱兑换 力扣题目链接 文章讲解322. 零钱兑换 视频讲解装满背包最少的物品件数是多少| LeetCode322.零钱兑换 在这里我先总结一下之前写过的题目
在518.零钱兑换II中我们求的是装满这个背包有多少种办法求的是不强调元素顺序的组合数递推公式是dp[j]dp[j-coins[i]]
在377. 组合总和 Ⅳ中我们也求的是装满这个背包有多少种方法但是求的是强调元素顺序的排列数递推公式也是dp[j]dp[j-coins[i]]但是我们的遍历顺序是外层for遍历背包内层for循环遍历物品
本题中我们求的是装满这个背包最少用多少件物品
思路
确定dp数组的含义
本题中要装满容量为account的背包最少的物品。那么很直观我们的dp数组的含义就是装满容量为j的背包所需要的最少物品数量为dp[j]
递推公式
首先我们放物品应该如何表达
如果我们要装满一个j-coins(i)容量大背包所需要的最少物品为dp[j-coins(i)]那我现在要装一个j容量的背包dp[j]可以有一种取值是dp[j] dp[j-coins(i)]1因为我们在遍历coins[i]那现在我要求一个装满j容量的最小值那肯定就是 d p [ j ] m i n ( d p [ j − c o i n s ( i ) ] 1 , d p [ j ] ) dp[j] min(dp[j-coins(i)]1, dp[j]) dp[j]min(dp[j−coins(i)]1,dp[j])
初始化
聊到初始化我们首先就要像dp[0]等于多少很明显根据题目含义account0的话我们什么都不放就可以凑成这个account了。
之前我们把非0下标的值初始成0是为了防止我们在递推公式求的值被初始值覆盖因为我们之前都是dpmax(...)但是在本题中我们的递推公式出现的是dp[j]min(...)所以我们应该把非零下标初始成INT_MAX。这样我们在推导赋值的时候才不会被初始值给覆盖掉
遍历顺序
还记得377. 组合总和 Ⅳ这篇文章遍历顺序部分我们做了一个小总结先遍历物品在遍历背包求的是组合数先遍历背包再遍历物品求的就是排列数。
在本题中我们求的是最少物品是多少所以本题和组合排列没什么关系不影响我们最终要求的最少的元素数量故本题什么样的遍历顺序都可以。
打印
以输入coins [1, 2, 5], amount 5为例 dp[amount]为最终结果。 CPP代码
// 版本一 先物品再背包
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount 1, INT_MAX);dp[0] 0;for (int i 0; i coins.size(); i) { // 遍历物品for (int j coins[i]; j amount; j) { // 遍历背包if (dp[j - coins[i]] ! INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过dp[j] min(dp[j - coins[i]] 1, dp[j]);}}}if (dp[amount] INT_MAX) return -1;return dp[amount];}
};// 版本二 先背包再物品
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount 1, INT_MAX);dp[0] 0;for (int i 1; i amount; i) { // 遍历背包for (int j 0; j coins.size(); j) { // 遍历物品if (i - coins[j] 0 dp[i - coins[j]] ! INT_MAX ) {dp[i] min(dp[i - coins[j]] 1, dp[i]);}}}if (dp[amount] INT_MAX) return -1;return dp[amount];}
};时间复杂度: O(n * amount)其中 n 为 coins 的长度空间复杂度: O(amount)
总结
装满背包最少要多少物品 的递推公式要重点关注再一个就是关于初始值的设定也很有讲究。
279.完全平方数 力扣题目链接 视频讲解换汤不换药| LeetCode279.完全平方数 文章讲解279.完全平方数 状态典型的背包问题真的就是换汤不换药 很明显我们这里的n就是我们的背包容量然后物品的重量和价值就是各个完全平方数题目中要求的是用完全平方数拼凑出n的最小个数这不就是妥妥的上一题 322.零钱兑换的思路也就是说求的是装满这个背包所需要的最少物品的数量
思路
dp数组的含义
看完上面对题目的论述本题直接j表示背包容量dp[j]表示能装满背包所需要的最少物品。
递归函数
跟上一题一样直接是dp[j] min(dp[j - i * i] 1, dp[j])
初始化
dp[0]表示 和为0的完全平方数的最小数量那么dp[0]一定是0。
同理从递归公式dp[j] min(dp[j - i * i] 1, dp[j])中可以看出每次dp[j]都要选最小的所以非0下标的dp[j]一定要初始为最大值INT_MAX这样dp[j]在递推的时候才不会被初始值覆盖。
遍历顺序
与上一题一样本题外层for遍历背包内层for遍历物品还是外层for遍历物品内层for遍历背包都是可以的
打印
略
CPP代码
// 版本一
class Solution {
public:int numSquares(int n) {vectorint dp(n 1, INT_MAX);dp[0] 0;for (int i 0; i n; i) { // 遍历背包for (int j 1; j * j i; j) { // 遍历物品dp[i] min(dp[i - j * j] 1, dp[i]);}}return dp[n];}
};// 版本二
class Solution {
public:int numSquares(int n) {vectorint dp(n 1, INT_MAX);dp[0] 0;for (int i 1; i * i n; i) { // 遍历物品for (int j i * i; j n; j) { // 遍历背包dp[j] min(dp[j - i * i] 1, dp[j]);}}return dp[n];}
};时间复杂度: O(n * √n)空间复杂度: O(n)
