# Day33 - 70.climbing stairs

## LeetCode 70.爬楼梯 <a href="#leetcode70-pa-lou-ti" id="leetcode70-pa-lou-ti"></a>

*题目链接：*

<https://leetcode.cn/problems/climbing-stairs/>

### 1. 题目描述 <a href="#ti-mu-miao-shu" id="ti-mu-miao-shu"></a>

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

**举个例子：**

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

### 2. 思路解析 <a href="#si-lu-jie-xi" id="si-lu-jie-xi"></a>

假设只有`4`个台阶，`0`阶代表地面。

![](https://2716872320-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9seebO0jUZDIXCUVBi9U%2Fuploads%2F3h8BkgLThTLQ2P9QafnO%2Fimage.png?alt=media\&token=11372fa2-3052-462b-a499-cff074c7d21e)

整个爬楼梯的过程对应的决策树可以表示成下图：

![](https://2716872320-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9seebO0jUZDIXCUVBi9U%2Fuploads%2F5O2FQCsDnTLubdIHRbMI%2Fimage.png?alt=media\&token=1c69e8f9-819d-4179-87ef-c7ab4c4bbe81)

**每个节点的值表示剩余的台阶数**，从根节点到叶子结点组成的路径代表一种爬楼梯的方法。

整个决策树存在递归结构，还存在重复子问题`两个节点2`、`三个节点1`，这些子问题计算一次后可以直接保存下来，避免多次重复计算。这就满足了使用动态规划的条件：**存在递归结构**和**子问题可以记忆化**。所以本题可以用**动态规划**来解

**动态规划**的两个核心点是**推导状态转移公式**和**边界处理**。

**定义`dp[i]`为`i`个台阶对应的爬楼梯的方法个数**。`dp[i]`的准确定义是推导状态转移公式的关键。

因为每次只能爬`1`或`2`个台阶，从上面的图可以看出`4`个台阶的爬楼梯方法可以拆解成`3`和`2`个台阶爬楼梯方法之和。说白了就是`节点4`到叶子`节点0`的所有路径等于`节点3`和`节点2`到叶子节点路径的总和。

$$
dp\[4] = dp\[3] + dp\[2]
$$

由`4`个台阶进一步扩展到`n`个台阶，我们得到下面的**状态转移公式**：&#x20;

$$
dp\[i] = dp\[i-1] + dp\[i-2], 1 < i <= n
$$

**接下来进行边界处理**，根据上面的公式可知 $$dp\[2] = dp\[1] + dp\[0]$$，很显然`dp[1] = 1`，`dp[2] = 2`，上面也说到`0`阶代表地面，为了写代码方便这里我们定义`dp[0] = 1`。

### 3. C++代码 <a href="#qters" id="qters"></a>

由于上楼梯的方式有两种：

* 上一阶和上两阶
* 所以得到递推公式 $$dp\[n] = dp\[n-1] （上一阶） + dp\[n-2]（上两阶）$$

```cpp
class Solution
{
public:
    int climbStairs(int n)
    {
        vector<int> dp(n+1, 0);
        // dp[0]表示第 0 阶台阶
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            // 递推公式
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};
```

上面的代码实现使用了一个长为`n+1`的`dp`数组，我们观察状态转移公式的规律，其实并不需要保存每个台阶数为`i`的爬楼梯方法，可以通过两个整型变量来优化上面的实现。![](https://2716872320-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F9seebO0jUZDIXCUVBi9U%2Fuploads%2FIgScsWAqrcqnwAhuVt9Q%2Fimage.png?alt=media\&token=1745166b-cb75-42d2-aab9-9fd6199d5788)

### 4. 代码优化 <a href="#yhpwr" id="yhpwr"></a>

```cpp
class Solution
{
public:
    int climbStairs(int n)
    {
        // pre表示第 0 阶台阶
        int pre = 1;
        int cur = 1;
        for (int i = 2; i <= n; i++)
        {
            int tmp = cur;
            // 减少空间复杂度
            cur = pre + cur;
            pre = tmp;
        }
        return cur;
    }
};
```

### 5. 复杂度分析 <a href="#vlt40" id="vlt40"></a>

**时间复杂度：** 两种实现方式的时间复杂度都是*O(n)*，`n`为台阶的个数。

**空间复杂度：** 第一种实现方式的空间复杂度为*O(n)*，`n`为台阶的个数。第二种实现方式的空间复杂度为*O(1)*。

### 6. Redo. 02/16 <a href="#uuepi" id="uuepi"></a>

自下而上的动态规划

```cpp
class Solution
{
public:
    int climbStairs(int n)
    {
        if(n == 1)
        {
            return 1;
        }
        vector<int> res(n, 0);
        res[0] = 1;
        res[1] = 2;
        for(int i = 2; i < n; i++)
        {
            res[i] = res[i-1] + res[i-2];
        }
        return res[n-1];
    }
};
```

滚动前进法

```cpp
class Solution
{
public:
    int climbStairs(int n)
    {
        if(n == 1)
        {
            return 1;
        }
        int cur = 2;
        int pre = 1;
        for(int i = 2; i < n; i++)
        {  
            int net = pre + cur;
            pre = cur;
            cur = net;
        }
        return cur;
    }
};
```
