爬楼梯系列篇

发表于 更新于 分类于 本文字数： 1.4k 阅读时长 ≈ 14 分钟

爬楼梯

Leetcode题目链接：70. 爬楼梯

题目简述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

解题思路

动态规划五部曲

  1. 定义dp[i]：表示踏上第i台阶有dp[i]种方法。
    1. dp[i-1]表示踏上第i-1台阶有dp[i-1]种方法，那么只要再踏上1步就是第i台阶
    2. dp[i-2]表示踏上第i-1台阶有dp[i-2]种方法，那么只要再踏上2步就是第i台阶
  2. 确定dp状态转移方程。 
    1
    dp[i] = dp[i-1] + dp[i-2]
  3. 初始化dp数组。
    1. dp[0]表示踏上第0台阶（那就是地面咯），所以dp[0]=1
    2. dp[1]表示踏上第1台阶，所以dp[1]=1
  4. 确定for循环长度、顺序、开始位置。
    1. 遍历长度为n
    2. 正序遍历
    3. 开始位置为2
  5. 举例推导dp数组

代码

1
2
3
4
5
6
7
8
9
public static int test(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

使用最小花费爬楼梯

Leetcode题目链接：746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
	
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

解题思路

动态规划五部曲：

  1. 确定dp[i]。dp[i]表示踏上第i台阶最低花费
    1. dp[i-1]：踏上第i-1台阶最低花费，那么只需要再爬1个台阶即可到达第i台阶，
      最低花费dp[i-1]+cost[i-1]
    2. dp[i-2]：踏上第i-2台阶最低花费，要到达到第i台阶则有两种方式：
      1. 一个一个台阶爬，花费dp[i-2]+cost[i-2]+cost[i-1]，这样花费肯定多
      2. 爬2个台阶，花费dp[i-2]+cost[i-2]
  2. 确定状态转移方程。求最低花费dp[i]，其实就是求dp[i-1]与dp[i-2]+cost[i]最小值 
    1
    dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
  3. 确定dp初始化。
    1. dp[0]表示从第0台阶（那就是地面咯）到楼顶最低花费，所以dp[0]=0
    2. dp[1]表示从第1台阶到楼顶最低花费，所以dp[1]=cost[0]
  4. 确定for循环长度、顺序、开始位置。
  5. 举例推导dp数组。

代码

1
2
3
4
5
6
7
8
9
10
public static int test(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 0;
    for (int i = 2; i <= n; i++) {
        dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[n];
}

爬楼梯（进阶版）

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

输入描述：输入共一行，包含两个正整数，分别表示n, m

输出描述：输出一个整数，表示爬到楼顶的方法数。

1
2
3
4
5
6
7
8
9
10
11
12
输入示例：3 2
输出示例：3

提示：
当 m = 2，n = 3 时，
n = 3 这表示一共有三个台阶，
m = 2 代表你每次可以爬一个台阶或者两个台阶。
此时你有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶段
1 阶 + 2 阶
2 阶 + 1 阶

解题思路

这里完全背包问题。

动态规划五部曲：

  1. 确定dp[i]。dp[i]表示踏上第i台阶有dp[i]种方法
    1. dp[i-j]：踏上第i-j台阶，那么只需要再爬j个台阶即可到达第i台阶，
      共dp[i-j]方式
  2. 确定状态转移方程。 
    1
    dp[i] += dp[i-j]
  3. 确定dp初始化。 p[0]表示踏上第0台阶（那就是地面咯），所以dp[0]=1
  4. 确定for循环长度、顺序、开始位置。
  5. 举例推导dp数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
public static int test(int n, int m) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i > j) {
                dp[i] += dp[i - j];
            }
        }
    }
    return dp[n];
}

项目地址

maozzi/algorithm项目源码