mirror of
https://github.com/youngyangyang04/leetcode-master.git
synced 2026-02-02 18:39:09 +08:00
253 lines
7.7 KiB
Markdown
Executable File
253 lines
7.7 KiB
Markdown
Executable File
* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
|
||
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
|
||
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)
|
||
|
||
# 70. 爬楼梯（进阶版）
|
||
|
||
[卡码网：57. 爬楼梯](https://kamacoder.com/problempage.php?pid=1067)
|
||
|
||
假设你正在爬楼梯。需要 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 阶
|
||
|
||
|
||
## 思路
|
||
|
||
之前讲这道题目的时候，因为还没有讲背包问题，所以就只是讲了一下爬楼梯最直接的动规方法（斐波那契）。
|
||
|
||
**这次终于讲到了背包问题，我选择带录友们再爬一次楼梯！**
|
||
|
||
这道题目 我们在[动态规划：爬楼梯](https://programmercarl.com/0070.爬楼梯.html) 中已经讲过一次了，这次我又给本题加点料，力扣上没有原题，所以可以在卡码网[57. 爬楼梯](https://kamacoder.com/problempage.php?pid=1067)上来刷这道题目。
|
||
|
||
我们之前做的 爬楼梯 是只能至多爬两个台阶。
|
||
|
||
这次**改为：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？**
|
||
|
||
这又有难度了，这其实是一个完全背包问题。
|
||
|
||
1阶，2阶，.... m阶就是物品，楼顶就是背包。
|
||
|
||
每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。
|
||
|
||
问跳到楼顶有几种方法其实就是问装满背包有几种方法。
|
||
|
||
**此时大家应该发现这就是一个完全背包问题了！**
|
||
|
||
和昨天的题目[动态规划：377. 组合总和 Ⅳ](https://programmercarl.com/0377.组合总和Ⅳ.html)基本就是一道题了。
|
||
|
||
动规五部曲分析如下：
|
||
|
||
1. 确定dp数组以及下标的含义
|
||
|
||
**dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法**。
|
||
|
||
2. 确定递推公式
|
||
|
||
在[动态规划：494.目标和](https://programmercarl.com/0494.目标和.html) 、 [动态规划：518.零钱兑换II](https://programmercarl.com/0518.零钱兑换II.html)、[动态规划：377. 组合总和 Ⅳ](https://programmercarl.com/0377.组合总和Ⅳ.html)中我们都讲过了，求装满背包有几种方法，递推公式一般都是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]
|
||
|
||
3. 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这样才不会影响结果
|
||
|
||
4. 确定遍历顺序
|
||
|
||
这是背包里求排列问题，即：**1、2 步 和 2、1 步都是上三个台阶，但是这两种方法不一样！**
|
||
|
||
所以需将target放在外循环，将nums放在内循环。
|
||
|
||
每一步可以走多次，这是完全背包，内循环需要从前向后遍历。
|
||
|
||
5. 举例来推导dp数组
|
||
|
||
介于本题和[动态规划：377. 组合总和 Ⅳ](https://programmercarl.com/0377.组合总和Ⅳ.html)几乎是一样的，这里我就不再重复举例了。
|
||
|
||
|
||
以上分析完毕，C++代码如下：
|
||
```CPP
|
||
#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;
|
||
}
|
||
}
|
||
```
|
||
|
||
* 时间复杂度: O(n * m)
|
||
* 空间复杂度: O(n)
|
||
|
||
代码中m表示最多可以爬m个台阶，代码中把m改成2就是 力扣：70.爬楼梯的解题思路。
|
||
|
||
**当然注意 力扣是 核心代码模式，卡码网是ACM模式**
|
||
|
||
|
||
## 总结
|
||
|
||
**本题看起来是一道简单题目，稍稍进阶一下其实就是一个完全背包！**
|
||
|
||
如果我来面试的话，我就会先给候选人出一个 本题原题，看其表现，如果顺利写出来，进而在要求每次可以爬[1 - m]个台阶应该怎么写。
|
||
|
||
顺便再考察一下两个for循环的嵌套顺序，为什么target放外面，nums放里面。
|
||
|
||
这就能考察对背包问题本质的掌握程度，候选人是不是刷题背公式，一眼就看出来了。
|
||
|
||
这么一连套下来，如果候选人都能答出来，相信任何一位面试官都是非常满意的。
|
||
|
||
**本题代码不长，题目也很普通，但稍稍一进阶就可以考察完全背包，而且题目进阶的内容在leetcode上并没有原题，一定程度上就可以排除掉刷题党了，简直是面试题目的绝佳选择！**
|
||
|
||
|
||
|
||
|
||
## 其他语言版本
|
||
|
||
### Java:
|
||
|
||
```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]);
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
### Python3：
|
||
```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))
|
||
```
|
||
|
||
|
||
### Go：
|
||
```go
|
||
package main
|
||
|
||
import (
|
||
"bufio"
|
||
"fmt"
|
||
"os"
|
||
"strconv"
|
||
"strings"
|
||
)
|
||
|
||
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)
|
||
}
|
||
```
|
||
|
||
### JavaScript:
|
||
```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];
|
||
}
|
||
```
|
||
|
||
### TypeScript：
|
||
```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];
|
||
}
|
||
```
|
||
|
||
### Rust:
|
||
|
||
|