70.爬楼梯

2023-04-19 2023-04-19 约 164 字预计阅读 1 分钟

系列 - LeetCode

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

题解

这道题是一个非常典型而且很简单的动态规划题目。我们可以根据动态规划题目解题的一般思路来分析：

定义状态：

$dp[i]$ 表示爬到第 $i$ 级楼梯的不同方法数。由于每次可以选择爬 $1$ 级或者 $2$ 级楼梯，所以爬到第 $i$ 级楼梯的方法数等于爬到第 $i-1$ 级楼梯和第 $i-2$ 级楼梯的方法数之和。根据这个关系，我们可以使用动态规划的方式从 $1$ 级楼梯开始逐步计算到第 $n$ 级楼梯的方法数，最终返回 $dp[n]$ 即为结果。

设计状态转移方程：

dp[i] = dp[i - 1] + dp[i - 2]

初始化：

由题目可知， $dp[0] = 0$ ; $dp[1] = 1$ ，这里需要特别注意的是， $dp[2] \ne dp[0] + dp[1]$ ，而是 $dp[2] = 2$ ，所以 $dp[2]$ 也应该作为初始值

递推求解：

#include <vector>

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

记忆优化：

从上面代码可以很容易发现，我们得出 $dp[i]$ 只需要用到 $dp[i - 1]$ 和 $dp[i -2]$ ，其他的元素其实都用不到，所以上面的代码可以优化为：

#include <vector>

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        int pp = 1;
        int p = 2;
        int c = 0;
        for (int i = 3; i <= n; ++i) {
            c = pp + p;
            pp = p;
            p = c;
        }
        return c;
    }
};

目录

目录

70.爬楼梯

题目描述

题解