Day33 - 70.climbing stairs

Day33 - 70.爬楼梯

LeetCode 70.爬楼梯

题目链接：

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

1. 题目描述

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

举个例子：

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

2. 思路解析

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

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

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

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

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

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

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

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

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

$$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++代码

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

• 上一阶和上两阶

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

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的爬楼梯方法，可以通过两个整型变量来优化上面的实现。

4. 代码优化

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. 复杂度分析

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

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

6. Redo. 02/16

自下而上的动态规划

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

滚动前进法

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