参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们受益!
# 70. 爬楼梯(进阶版)
卡码网:57. 爬楼梯 (opens new window)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
输入描述:输入共一行,包含两个正整数,分别表示n, m
输出描述:输出一个整数,表示爬到楼顶的方法数。
输入示例:3 2
输出示例:3
提示:
当 m = 2,n = 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] 一定为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. 组合总和 Ⅳ (opens new window)几乎是一样的,这里我就不再重复举例了。
以上分析完毕,C++代码如下:
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
while (cin >> n >> m) {
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];
}
}
cout << dp[n] << endl;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
- 时间复杂度: O(n * m)
- 空间复杂度: O(n)
代码中m表示最多可以爬m个台阶,代码中把m改成2就是 力扣:70.爬楼梯的解题思路。
当然注意 力扣是 核心代码模式,卡码网是ACM模式
# 总结
本题看起来是一道简单题目,稍稍进阶一下其实就是一个完全背包!
如果我来面试的话,我就会先给候选人出一个 本题原题,看其表现,如果顺利写出来,进而在要求每次可以爬[1 - m]个台阶应该怎么写。
顺便再考察一下两个for循环的嵌套顺序,为什么target放外面,nums放里面。
这就能考察对背包问题本质的掌握程度,候选人是不是刷题背公式,一眼就看出来了。
这么一连套下来,如果候选人都能答出来,相信任何一位面试官都是非常满意的。
本题代码不长,题目也很普通,但稍稍一进阶就可以考察完全背包,而且题目进阶的内容在leetcode上并没有原题,一定程度上就可以排除掉刷题党了,简直是面试题目的绝佳选择!
# 其他语言版本
# Java:
import java.util.Scanner;
class climbStairs{
public static void main(String [] args){
Scanner sc = new Scanner(System.in);
int m, n;
while (sc.hasNextInt()) {
// 从键盘输入参数,中间用空格隔开
n = sc.nextInt();
m = sc.nextInt();
// 求排列问题,先遍历背包再遍历物品
int[] dp = new int[n + 1];
dp[0] = 1;
for (int j = 1; j <= n; j++) {
for (int i = 1; i <= m; i++) {
if (j - i >= 0) dp[j] += dp[j - i];
}
}
System.out.println(dp[n]);
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Python3:
def climbing_stairs(n,m):
dp = [0]*(n+1) # 背包总容量
dp[0] = 1
# 排列题,注意循环顺序,背包在外物品在内
for j in range(1,n+1):
for i in range(1,m+1):
if j>=i:
dp[j] += dp[j-i] # 这里i就是重量而非index
return dp[n]
if __name__ == '__main__':
n,m = list(map(int,input().split(' ')))
print(climbing_stairs(n,m))
2
3
4
5
6
7
8
9
10
11
12
13
# Go:
func climbStairs(n int, m int) int {
dp := make([]int, n+1)
dp[0] = 1
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
if i-j >= 0 {
dp[i] += dp[i-j]
}
}
}
return dp[n]
}
func main() {
// 读取输入n,m
reader := bufio.NewReader(os.Stdin)
input, _ := reader.ReadString('\n')
input = strings.TrimSpace(input)
nv := strings.Split(input, " ")
n, _ := strconv.Atoi(nv[0])
m, _ := strconv.Atoi(nv[1])
result := climbStairs(n, m)
fmt.Println(result)
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# JavaScript:
var climbStairs = function (n) {
let dp = new Array(n + 1).fill(0);
dp[0] = 1;
// 排列题,注意循环顺序,背包在外物品在内
for (let j = 1; j <= n; j++) {//遍历背包
for (let i = 1; i <= 2; i++) {//遍历物品
if (j - i >= 0) dp[j] = dp[j] + dp[j - i];
}
}
return dp[n];
}
2
3
4
5
6
7
8
9
10
11
# TypeScript:
var climbStairs = function (n: number): number {
let dp: number[] = new Array(n + 1).fill(0);
dp[0] = 1;
for (let j = 1; j <= n; j++) {//遍历背包
for (let i = 1; i <= 2; i++) {//遍历物品
if (j - i >= 0) dp[j] = dp[j] + dp[j - i];
}
}
return dp[n];
}
2
3
4
5
6
7
8
9
10