程序员必学算法「动态规划」:爬楼梯(完全背包解法)
通知:我将公众号文章和学习相关的资料整理到了Github :https://github.com/youngyangyang04/leetcode-master,方便大家在电脑上学习,可以fork到自己仓库,顺便也给个star支持一波吧!
之前讲这道题目的时候,因为还没有讲背包问题,所以就只是讲了一下爬楼梯最直接的动规方法(斐波那契)。
这次终于讲到了背包问题,我选择带录友们再爬一次楼梯!
此情此景,借用一下《无间道》的台词 哈哈哈。
70. 爬楼梯
链接:https://leetcode-cn.com/problems/climbing-stairs/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
输入:2
输出:2
解释:有两种方法可以爬到楼顶。
1 阶 1 阶
2 阶
示例 2:
输入:3
输出:3
解释:有三种方法可以爬到楼顶。
1 阶 1 阶 1 阶
1 阶 2 阶
2 阶 1 阶
思路
这道题目 我们在动态规划:爬楼梯 中已经讲过一次了,原题其实是一道简单动规的题目。
既然这么简单为什么还要讲呢,其实本题稍加改动就是一道面试好题。
改为:每次可以爬 1 、 2或者m 个台阶。问有多少种不同的方法可以爬到楼顶呢?
1阶,2阶,m阶就是物品,楼顶就是背包。
每一阶可以重复使用,例如跳了1阶,还可以继续跳1阶。
问跳到楼顶有几种方法其实就是问装满背包有几种方法。
此时大家应该发现这就是一个完全背包问题了!
和昨天的题目动态规划:377. 组合总和 Ⅳ基本就是一道题了。
动规五部曲分析如下:
确定dp数组以及下标的含义
dp[i]:爬到有i个台阶的楼顶,有dp[i]种方法。
确定递推公式
在动态规划:494.目标和 、 动态规划:518.零钱兑换II、动态规划:377. 组合总和 Ⅳ中我们都讲过了,求装满背包有几种方法,递推公式一般都是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] 一定为1,dp[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. 组合总和 Ⅳ几乎是一样的,这里我就不再重复举例了。
以上分析完毕,C 代码如下:
class Solution {public: int climbStairs(int n) { 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 >= 0) dp[i] = dp[i - j]; } } return dp[n]; }};
代码中m表示最多可以爬m个台阶,代码中把m改成2就是本题70.爬楼梯可以AC的代码了。
总结
本题看起来是一道简单题目,稍稍进阶一下其实就是一个完全背包!
如果我来面试的话,我就会先给候选人出一个 本题原题,看其表现,如果顺利写出来,进而在要求每次可以爬[1 - m]个台阶应该怎么写。
顺便再考察一下两个for循环的嵌套顺序,为什么target放外面,nums放里面。
这就能考察对背包问题本质的掌握程度,候选人是不是刷题背公式,一眼就看出来了。
这么一连套下来,如果候选人都能答出来,相信任何一位面试官都是非常满意的。
本题代码不长,题目也很普通,但稍稍一进阶就可以考察完全背包,而且题目进阶的内容在leetcode上并没有原题,一定程度上就可以排除掉刷题党了,简直是面试题目的绝佳选择!
力扣刷题指南:https://github.com/youngyangyang04/leetcode-master