南昌网站排名推广,投资建设集团网站首页,如何做木工雕刻机网站,wordpress评论vip70. 爬楼梯#xff08;进阶版#xff09;
卡码网#xff1a;57. 爬楼梯(opens new window)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 m n)个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
注意#xff1a;给定 n 是一个正…70. 爬楼梯进阶版
卡码网57. 爬楼梯(opens new window)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 m n)个台阶。你有多少种不同的方法可以爬到楼顶呢
注意给定 n 是一个正整数。
输入描述输入共一行包含两个正整数分别表示n, m
输出描述输出一个整数表示爬到楼顶的方法数。
输入示例3 2
输出示例3
提示
当 m 2n 3 时n 3 这表示一共有三个台阶m 2 代表你每次可以爬一个台阶或者两个台阶。
此时你有三种方法可以爬到楼顶。
1 阶 1 阶 1 阶段 1 阶 2 阶 2 阶 1 阶
思路
之前讲这道题目的时候因为还没有讲背包问题所以就只是讲了一下爬楼梯最直接的动规方法斐波那契。
这次终于讲到了背包问题我选择带录友们再爬一次楼梯
这道题目 我们在动态规划爬楼梯 (opens new window)中已经讲过一次了这次我又给本题加点料力扣上没有原题所以可以在卡码网57. 爬楼梯 (opens new window)上来刷这道题目。
我们之前做的 爬楼梯 是只能至多爬两个台阶。
这次改为一步一个台阶两个台阶三个台阶…直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢
这又有难度了这其实是一个完全背包问题。
1阶2阶… m阶就是物品楼顶就是背包。
每一阶可以重复使用例如跳了1阶还可以继续跳1阶。
问跳到楼顶有几种方法其实就是问装满背包有几种方法。
此时大家应该发现这就是一个完全背包问题了
和昨天的题目动态规划377. 组合总和 Ⅳ (opens new window)基本就是一道题了。
动规五部曲分析如下
确定dp数组以及下标的含义 dp[i]爬到有i个台阶的楼顶有dp[i]种方法。
确定递推公式 在动态规划494.目标和 (opens new window)、 动态规划518.零钱兑换II (opens new window)、动态规划377. 组合总和 Ⅳ (opens new window)中我们都讲过了求装满背包有几种方法递推公式一般都是dp[i] dp[i - nums[j]];
本题呢dp[i]有几种来源dp[i - 1]dp[i - 2]dp[i - 3] 等等即dp[i - j]
那么递推公式为dp[i] dp[i - j]
dp数组如何初始化 既然递归公式是 dp[i] dp[i - j]那么dp[0] 一定为1dp[0]是递归中一切数值的基础所在如果dp[0]是0的话其他数值都是0了。
下标非0的dp[i]初始化为0因为dp[i]是靠dp[i-j]累计上来的dp[i]本身为0这样才不会影响结果
确定遍历顺序 这是背包里求排列问题即1、2 步 和 2、1 步都是上三个台阶但是这两种方法不一样
所以需将target放在外循环将nums放在内循环。
每一步可以走多次这是完全背包内循环需要从前向后遍历。
举例来推导dp数组 介于本题和动态规划377. 组合总和 Ⅳ (opens new window)几乎是一样的这里我就不再重复举例了。
以上分析完毕C代码如下
#include iostream
#include vector
using namespace std;
int main() {int n, m;while (cin n m) {vectorint dp(n 1, 0);dp[0] 1;for (int i 1; i n; i) { // 遍历物品for (int j 1; j m; j) { // 遍历背包if (i - j 0) dp[i] dp[i - j];}}cout dp[n] endl;}
}322. 零钱兑换
力扣题目链接(opens new window)
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1
输入coins [1, 2, 5], amount 11 输出3 解释11 5 5 1 示例 2
输入coins [2], amount 3 输出-1 示例 3
输入coins [1], amount 0 输出0 示例 4
输入coins [1], amount 1 输出1 示例 5
输入coins [1], amount 2 输出2 提示
1 coins.length 12 1 coins[i] 2^31 - 1 0 amount 10^4
思路
在动态规划518.零钱兑换II (opens new window)中我们已经兑换一次零钱了这次又要兑换套路不一样
题目中说每种硬币的数量是无限的可以看出是典型的完全背包问题。
动规五部曲分析如下
确定dp数组以及下标的含义 dp[j]凑足总额为j所需钱币的最少个数为dp[j]
确定递推公式 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]那么只需要加上一个钱币coins[i]即dp[j - coins[i]] 1就是dp[j]考虑coins[i]
所以dp[j] 要取所有 dp[j - coins[i]] 1 中最小的。
递推公式dp[j] min(dp[j - coins[i]] 1, dp[j]);
dp数组如何初始化 首先凑足总金额为0所需钱币的个数一定是0那么dp[0] 0;
其他下标对应的数值呢
考虑到递推公式的特性dp[j]必须初始化为一个最大的数否则就会在min(dp[j - coins[i]] 1, dp[j])比较的过程中被初始值覆盖。
所以下标非0的元素都是应该是最大值。
代码如下
vectorint dp(amount 1, INT_MAX);
dp[0] 0;确定遍历顺序 本题求钱币最小个数那么钱币有顺序和没有顺序都可以都不影响钱币的最小个数。
所以本题并不强调集合是组合还是排列。
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
在动态规划专题我们讲过了求组合数是动态规划518.零钱兑换II (opens new window)求排列数是动态规划377. 组合总和 Ⅳ (opens new window)。
所以本题的两个for循环的关系是外层for循环遍历物品内层for遍历背包或者外层for遍历背包内层for循环遍历物品都是可以的
那么我采用coins放在外循环target在内循环的方式。
本题钱币数量可以无限使用那么是完全背包。所以遍历的内循环是正序
综上所述遍历顺序为coins物品放在外循环target背包在内循环。且内循环正序。
举例推导dp数组 以输入coins [1, 2, 5], amount 5为例 dp[amount]为最终结果。
以上分析完毕C 代码如下
// 版本一
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];}
};时间复杂度: O(n * amount)其中 n 为 coins 的长度 空间复杂度: O(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];}
};Python 先遍历物品 后遍历背包
class Solution:def coinChange(self, coins: List[int], amount: int) - int:dp [float(inf)] * (amount 1) # 创建动态规划数组初始值为正无穷大dp[0] 0 # 初始化背包容量为0时的最小硬币数量为0for coin in coins: # 遍历硬币列表相当于遍历物品for i in range(coin, amount 1): # 遍历背包容量if dp[i - coin] ! float(inf): # 如果dp[i - coin]不是初始值则进行状态转移dp[i] min(dp[i - coin] 1, dp[i]) # 更新最小硬币数量if dp[amount] float(inf): # 如果最终背包容量的最小硬币数量仍为正无穷大表示无解return -1return dp[amount] # 返回背包容量为amount时的最小硬币数量先遍历背包 后遍历物品
class Solution:def coinChange(self, coins: List[int], amount: int) - int:dp [float(inf)] * (amount 1) # 创建动态规划数组初始值为正无穷大dp[0] 0 # 初始化背包容量为0时的最小硬币数量为0for i in range(1, amount 1): # 遍历背包容量for j in range(len(coins)): # 遍历硬币列表相当于遍历物品if i - coins[j] 0 and dp[i - coins[j]] ! float(inf): # 如果dp[i - coins[j]]不是初始值则进行状态转移dp[i] min(dp[i - coins[j]] 1, dp[i]) # 更新最小硬币数量if dp[amount] float(inf): # 如果最终背包容量的最小硬币数量仍为正无穷大表示无解return -1return dp[amount] # 返回背包容量为amount时的最小硬币数量先遍历物品 后遍历背包优化版
class Solution:def coinChange(self, coins: List[int], amount: int) - int:dp [float(inf)] * (amount 1)dp[0] 0for coin in coins:for i in range(coin, amount 1): # 进行优化从能装得下的背包开始计算则不需要进行比较# 更新凑成金额 i 所需的最少硬币数量dp[i] min(dp[i], dp[i - coin] 1)return dp[amount] if dp[amount] ! float(inf) else -1先遍历背包 后遍历物品优化版
class Solution:def coinChange(self, coins: List[int], amount: int) - int:dp [float(inf)] * (amount 1)dp[0] 0for i in range(1, amount 1): # 遍历背包容量for coin in coins: # 遍历物品if i - coin 0:# 更新凑成金额 i 所需的最少硬币数量dp[i] min(dp[i], dp[i - coin] 1)return dp[amount] if dp[amount] ! float(inf) else -1279.完全平方数
力扣题目链接(opens new window)
给定正整数 n找到若干个完全平方数比如 1, 4, 9, 16, …使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n 返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。
示例 1
输入n 12 输出3 解释12 4 4 4 示例 2
输入n 13 输出2 解释13 4 9 提示
1 n 10^4
思路
可能刚看这种题感觉没啥思路又平方和的又最小数的。
我来把题目翻译一下完全平方数就是物品可以无限件使用凑个正整数n就是背包问凑满这个背包最少有多少物品
感受出来了没这么浓厚的完全背包氛围而且和昨天的题目动态规划322. 零钱兑换 (opens new window)就是一样一样的
动规五部曲分析如下
确定dp数组dp table以及下标的含义 dp[j]和为j的完全平方数的最少数量为dp[j]
确定递推公式 dp[j] 可以由dp[j - i * i]推出 dp[j - i * i] 1 便可以凑成dp[j]。
此时我们要选择最小的dp[j]所以递推公式dp[j] min(dp[j - i * i] 1, dp[j]);
dp数组如何初始化 dp[0]表示 和为0的完全平方数的最小数量那么dp[0]一定是0。
有同学问题那0 * 0 也算是一种啊为啥dp[0] 就是 0呢
看题目描述找到若干个完全平方数比如 1, 4, 9, 16, …题目描述中可没说要从0开始dp[0]0完全是为了递推公式。
非0下标的dp[j]应该是多少呢
从递归公式dp[j] min(dp[j - i * i] 1, dp[j]);中可以看出每次dp[j]都要选最小的所以非0下标的dp[j]一定要初始为最大值这样dp[j]在递推的时候才不会被初始值覆盖。
确定遍历顺序 我们知道这是完全背包
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
在动态规划322. 零钱兑换 (opens new window)中我们就深入探讨了这个问题本题也是一样的是求最小数
所以本题外层for遍历背包内层for遍历物品还是外层for遍历物品内层for遍历背包都是可以的
我这里先给出外层遍历背包内层遍历物品的代码
ectorint 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]);}
}举例推导dp数组 已输入n为5例dp状态图如下 dp[0] 0 dp[1] min(dp[0] 1) 1 dp[2] min(dp[1] 1) 2 dp[3] min(dp[2] 1) 3 dp[4] min(dp[3] 1, dp[0] 1) 1 dp[5] min(dp[4] 1, dp[1] 1) 2
最后的dp[n]为最终结果。
以上动规五部曲分析完毕C代码如下
// 版本一
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];}
};时间复杂度: O(n * √n) 空间复杂度: O(n) 同样我在给出先遍历物品在遍历背包的代码一样的可以AC的。
// 版本二
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];}
};Python 先遍历物品, 再遍历背包
class Solution:def numSquares(self, n: int) - int:dp [float(inf)] * (n 1)dp[0] 0for i in range(1, n 1): # 遍历背包for j in range(1, int(i ** 0.5) 1): # 遍历物品# 更新凑成数字 i 所需的最少完全平方数数量dp[i] min(dp[i], dp[i - j * j] 1)return dp[n]先遍历背包, 再遍历物品
class Solution:def numSquares(self, n: int) - int:dp [float(inf)] * (n 1)dp[0] 0for i in range(1, int(n ** 0.5) 1): # 遍历物品for j in range(i * i, n 1): # 遍历背包# 更新凑成数字 j 所需的最少完全平方数数量dp[j] min(dp[j - i * i] 1, dp[j])return dp[n]其他版本
class Solution:def numSquares(self, n: int) - int:# 创建动态规划数组初始值为最大值dp [float(inf)] * (n 1)# 初始化已知情况dp[0] 0# 遍历背包容量for i in range(1, n 1):# 遍历完全平方数作为物品j 1while j * j i:# 更新最少完全平方数的数量dp[i] min(dp[i], dp[i - j * j] 1)j 1# 返回结果return dp[n]
