爬楼梯

509. Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints:

  • 0 <= n <= 30

思路

动态规划五部曲：

这里我们要用一个一维dp数组来保存递归的结果

  1. 确定dp数组以及下标的含义

dp[i]的定义为：第i个数的斐波那契数值是dp[i]

  1. 确定递推公式

为什么这是一道非常简单的入门题目呢？

因为题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

  1. dp数组如何初始化

题目中把如何初始化也直接给我们了，如下：

dp[0] = 0;
dp[1] = 1;

  1. 确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

  1. 举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

C++解法

当然可以发现，我们只需要维护两个数值就可以了，不需要记录整个序列。

状态压缩版代码如下：

class Solution {  
public:  
    int fib(int N) {  
        if (N <= 1) return N;  
        int dp[2];  
        dp[0] = 0;  
        dp[1] = 1;  
        for (int i = 2; i <= N; i++) {  
            int sum = dp[0] + dp[1];  
            dp[0] = dp[1];  
            dp[1] = sum;  
        }  
        return dp[1];  
    }  
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

Java解法

class Solution {
    public int fib(int n) {
        if(n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.

  1. 1 step + 1 step
  2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.

  1. 1 step + 1 step + 1 step
  2. 1 step + 2 steps
  3. 2 steps + 1 step

Constraints:

  • 1 <= n <= 45

思路

本题大家如果没有接触过的话，会感觉比较难，多举几个例子，就可以发现其规律。

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯和到第一层楼梯状态推导出来，那么就可以想到动态规划了。

我们来分析一下，动规五部曲：

定义一个一维数组来记录不同楼层的状态

  1. 确定dp数组以及下标的含义

dp[i]： 爬到第i层楼梯，有dp[i]种方法

  1. 确定递推公式

如何可以推出dp[i]呢？

从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。

首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。

还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。

那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！

所以dp[i] = dp[i - 1] + dp[i - 2] 。

在推导dp[i]的时候，一定要时刻想着dp[i]的定义，否则容易跑偏。

这体现出确定dp数组以及下标的含义的重要性！

  1. dp数组如何初始化

再回顾一下dp[i]的定义：爬到第i层楼梯，有dp[i]种方法。

那么i为0，dp[i]应该是多少呢，这个可以有很多解释，但基本都是直接奔着答案去解释的。

例如强行安慰自己爬到第0层，也有一种方法，什么都不做也就是一种方法即：dp[0] = 1，相当于直接站在楼顶。

但总有点牵强的成分。

那还这么理解呢：我就认为跑到第0层，方法就是0啊，一步只能走一个台阶或者两个台阶，然而楼层是0，直接站楼顶上了，就是不用方法，dp[0]就应该是0.

其实这么争论下去没有意义，大部分解释说dp[0]应该为1的理由其实是因为dp[0]=1的话在递推的过程中i从2开始遍历本题就能过，然后就往结果上靠去解释dp[0] = 1。

从dp数组定义的角度上来说，dp[0] = 0 也能说得通。

需要注意的是：题目中说了n是一个正整数，题目根本就没说n有为0的情况。

所以本题其实就不应该讨论dp[0]的初始化！

我相信dp[1] = 1，dp[2] = 2，这个初始化大家应该都没有争议的。

所以我的原则是：不考虑dp[0]如何初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。

  1. 确定遍历顺序

从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的

  1. 举例推导dp数组

举例当n为5的时候，dp table（dp数组）应该是这样的

如果代码出问题了，就把dp table 打印出来，看看究竟是不是和自己推导的一样。

此时大家应该发现了，这不就是斐波那契数列么！

唯一的区别是，没有讨论dp[0]应该是什么，因为dp[0]在本题没有意义！

C++解法

以上五部分析完之后，C++代码如下：

// 版本一  
class Solution {  
public:  
    int climbStairs(int n) {  
        if (n <= 1) return n; // 因为下面直接对dp[2]操作了，防止空指针  
        vector<int> dp(n + 1);  
        dp[1] = 1;  
        dp[2] = 2;  
        for (int i = 3; i <= n; i++) { // 注意i是从3开始的  
            dp[i] = dp[i - 1] + dp[i - 2];  
        }  
        return dp[n];  
    }  
};
  • 时间复杂度：
  • 空间复杂度：

当然依然也可以，优化一下空间复杂度，代码如下：

// 版本二  
class Solution {  
public:  
    int climbStairs(int n) {  
        if (n <= 1) return n;  
        int dp[3];  
        dp[1] = 1;  
        dp[2] = 2;  
        for (int i = 3; i <= n; i++) {  
            int sum = dp[1] + dp[2];  
            dp[1] = dp[2];  
            dp[2] = sum;  
        }  
        return dp[2];  
    }  
};
  • 时间复杂度：
  • 空间复杂度：

后面将讲解的很多动规的题目其实都是当前状态依赖前两个，或者前三个状态，都可以做空间上的优化，但我个人认为面试中能写出版本一就够了哈，清晰明了，如果面试官要求进一步优化空间的话，我们再去优化。

因为版本一才能体现出动规的思想精髓，递推的状态变化。

Java解法

class Solution {
    public int climbStairs(int n) {
        if(n <= 3) return n;
        int[] dp = new int[n + 1];
        dp[2] = 2;
        dp[3] = 3;
        for(int i = 4; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

746. Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.

  • Pay 15 and climb two steps to reach the top. The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.

  • Pay 1 and climb two steps to reach index 2.
  • Pay 1 and climb two steps to reach index 4.
  • Pay 1 and climb two steps to reach index 6.
  • Pay 1 and climb one step to reach index 7.
  • Pay 1 and climb two steps to reach index 9.
  • Pay 1 and climb one step to reach the top. The total cost is 6.

Constraints:

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999

思路

修改之后的题意就比较明确了，题目中说 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯” 也就是相当于 跳到 下标 0 或者 下标 1 是不花费体力的， 从 下标 0 下标1 开始跳就要花费体力了。

  1. 确定dp数组以及下标的含义

使用动态规划，就要有一个数组来记录状态，本题只需要一个一维数组dp[i]就可以了。

dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。

对于dp数组的定义，大家一定要清晰！

  1. 确定递推公式

可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？

一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

  1. dp数组如何初始化

看一下递归公式，dp[i]由dp[i - 1]，dp[i - 2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0]dp[1]推出。

那么 dp[0] 应该是多少呢？ 根据dp数组的定义，到达第0台阶所花费的最小体力为dp[0]，那么有同学可能想，那dp[0] 应该是 cost[0]，例如 cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 的话，dp[0] 就是 cost[0] 应该是1。

这里就要说明本题力扣为什么改题意，而且修改题意之后 就清晰很多的原因了。

新题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的，但从 第0 个台阶 往上跳的话，需要花费 cost[0]。

所以初始化 dp[0] = 0，dp[1] = 0;

  1. 确定遍历顺序

最后一步，递归公式有了，初始化有了，如何遍历呢？

本题的遍历顺序其实比较简单，简单到很多同学都忽略了思考这一步直接就把代码写出来了。

因为是模拟台阶，而且dp[i]由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。

但是稍稍有点难度的动态规划，其遍历顺序并不容易确定下来。 例如：01背包，都知道两个for循环，一个for遍历物品嵌套一个for遍历背包容量，那么为什么不是一个for遍历背包容量嵌套一个for遍历物品呢？ 以及在使用一维dp数组的时候遍历背包容量为什么要倒序呢？

这些都与遍历顺序息息相关。当然背包问题后续「代码随想录」都会重点讲解的！

  1. 举例推导dp数组

拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下：

如果大家代码写出来有问题，就把dp数组打印出来，看看和如上推导的是不是一样的。

C++解法

以上分析完毕，整体C++代码如下：

class Solution {  
public:  
    int minCostClimbingStairs(vector<int>& cost) {  
        vector<int> dp(cost.size() + 1);  
        dp[0] = 0; // 默认第一步都是不花费体力的  
        dp[1] = 0;  
        for (int i = 2; i <= cost.size(); i++) {  
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);  
        }  
        return dp[cost.size()];  
    }  
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

还可以优化空间复杂度，因为dp[i]就是由前两位推出来的，那么也不用dp数组了，C++代码如下：

class Solution {  
public:  
    int minCostClimbingStairs(vector<int>& cost) {  
        int dp0 = 0;  
        int dp1 = 0;  
        for (int i = 2; i <= cost.size(); i++) {  
            int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]);  
            dp0 = dp1; // 记录一下前两位  
            dp1 = dpi;  
        }  
        return dp1;  
    }  
};

​

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

当然如果在面试中，能写出版本一就行，除非面试官额外要求空间复杂度，那么再去思考版本二，因为版本二还是有点绕。版本一才是正常思路。

70. 爬楼梯（进阶版）

卡码网：57. 爬楼梯

假设你正在爬楼梯。需要 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 阶

思路

之前讲这道题目的时候，因为还没有讲背包问题，所以就只是讲了一下爬楼梯最直接的动规方法（斐波那契）。

这次终于讲到了背包问题，我选择带录友们再爬一次楼梯！

这道题目 我们在动态规划：爬楼梯 中已经讲过一次了，这次我又给本题加点料，力扣上没有原题，所以可以在卡码网57. 爬楼梯上来刷这道题目。

我们之前做的 爬楼梯 是只能至多爬两个台阶。

这次改为：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？

这又有难度了，这其实是一个完全背包问题。

1阶，2阶，.... m阶就是物品，楼顶就是背包。

每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。

问跳到楼顶有几种方法其实就是问装满背包有几种方法。

此时大家应该发现这就是一个完全背包问题了！

和昨天的题目动态规划：377. 组合总和 Ⅳ基本就是一道题了。

动规五部曲分析如下：

  1. 确定dp数组以及下标的含义

dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。

  1. 确定递推公式

在动态规划：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]

  1. 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. 确定遍历顺序

这是背包里求排列问题，即：1、2 步 和 2、1 步都是上三个台阶，但是这两种方法不一样！

所以需将target放在外循环，将nums放在内循环。

每一步可以走多次，这是完全背包，内循环需要从前向后遍历。

  1. 举例来推导dp数组

介于本题和动态规划：377. 组合总和 Ⅳ几乎是一样的，这里我就不再重复举例了。

总结

本题看起来是一道简单题目，稍稍进阶一下其实就是一个完全背包！

如果我来面试的话，我就会先给候选人出一个本题原题，看其表现，如果顺利写出来，进而在要求每次可以爬[1 - m]个台阶应该怎么写。

顺便再考察一下两个for循环的嵌套顺序，为什么target放外面，nums放里面。

这就能考察对背包问题本质的掌握程度，候选人是不是刷题背公式，一眼就看出来了。

这么一连套下来，如果候选人都能答出来，相信任何一位面试官都是非常满意的。

本题代码不长，题目也很普通，但稍稍一进阶就可以考察完全背包，而且题目进阶的内容在leetcode上并没有原题，一定程度上就可以排除掉刷题党了，简直是面试题目的绝佳选择！

C++解法

以上分析完毕，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;  
    }  
}
  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n)

代码中m表示最多可以爬m个台阶，代码中把m改成2就是 力扣：70.爬楼梯的解题思路。

当然注意 力扣是 核心代码模式，卡码网是ACM模式

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]);  
        }  
    }  
}