算法-分析爬楼梯问题从递归-＞记忆化搜索-＞动态规划

短命女 2023-01-13 10:47 145阅读 0赞

### 文章目录 ###

*  爬楼梯问题
 *  1.递归思想分析问题
 *   *  代码实现
     *  存在的问题
 *  2.记忆化搜索
 *  3.记忆化搜索转化为动态规划

# 爬楼梯问题 #

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

例子：

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

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

# 1.递归思想分析问题 #

那么站在第 n 阶楼梯这个视角， 有哪些后退的可能性呢？按照题目中的要求，一次只能后退 1 步或者 2 步。因此可以定位到从第 n 阶楼梯只能后退到第 n-1 或者第 n-2 阶。我们把抵达第 n-1 阶楼梯对应的路径数记为f(n-1)，把抵达第 n-2 阶楼梯对应的路径数记为 f(n-2)，不难得出以下关系：

f(n) = f(n-1) + f(n-2)

同理：

f(n-1) = f(n-2) + f(n-3)

可以用这样一个树结构表示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTAzNTY3_size_16_color_FFFFFF_t_70]  
随着拆分的进行，一定会有一个时刻，求解到了 f(1) 或 f(2)。按照题设规则，第 1 阶楼梯只能走 1 步抵达，第 2 阶楼梯可以走 1 步或者走 2 步抵达，因此我们不难得出 f(1) 和 f(2) 的值：

f(1) = 1   
    f(2) = 2

## 代码实现 ##

递归出口：

f(1) = 1   
    f(2) = 2

递归式为：`f(n) = f(n-1) + f(n-2)`

所以可以写出递归代码：

/**
    * @param {number} n
    * @return {number}
    */
    const climbStairs = function(n) {
        // 处理递归边界
        if(n === 1) {
            return 1
        }
        if(n === 2){
            return 2
        }
        // 递归计算
        return climbStairs(n-1) + climbStairs(n-2)
    };

## 存在的问题 ##

递归解法问题比较大，丢进 OJ 会直接超时。我们一起来看看原因，回到我们上面这张树形结构图上来：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTAzNTY3_size_16_color_FFFFFF_t_70 1]  
f(n-2) 和f(n-3)标红了。大家不难看出，我们在图中对 f(n-2)和f(n-3) 进行了重复的计算。

随着我们递归层级的加深，这个重复的问题会越来越严重：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTAzNTY3_size_16_color_FFFFFF_t_70 2]

# 2.记忆化搜索 #

重复计算带来了时间效率上的问题，要想解决这类问题，最直接的思路就是用空间换时间，也就是想办法记住之前已经求解过的结果。这里我们只需要定义一个数组：

const f = []

每计算出一个 f(n) 的值，都把它塞进 f 数组里。下次要用到这个值的时候，直接取出来就行了：

/**
    * @param {number} n
    * @return {number}
    */
    // 定义记忆数组 f
    const f = []
    const climbStairs = function(n) {
      if(n==1) {
          return 1
      }
      if(n==2) {
          return 2
      }
      // 若f[n]不存在，则进行计算
      if(f[n]===undefined)  f[n] = climbStairs(n-1) + climbStairs(n-2)
      // 若f[n]已经求解过，直接返回
      return f[n]
    };

以上这种在递归的过程中，不断保存已经计算出的结果，从而避免重复计算的手法，就是**记忆化搜索**。

# 3.记忆化搜索转化为动态规划 #

要想完成记忆化搜索与动态规划之间的转化，首先要清楚两者间的区别。

*  记忆化搜索：**记忆化搜索可以理解为优化过后的递归**。递归往往可以基于树形思维模型来做，这个过程是一个明显的**自顶向下**的过程。
 *  动态规划则恰恰相反，是一个**自底向上**的过程。它要求我们站在已知的角度，通过定位已知和未知之间的关系，一步一步向前推导，进而求解出未知的值。

根据这个关系往上推

f(3) = f(2) + f(1)
    f(4) = f(3) + f(2)
    ......
    f(n) = f(n-1) + f(n-2)

动态规划中三个重要的概念：**最优子结构、边界、状态转移公式**

F(1) = 1; 边界
    
    F(2) = 2; 边界
    
    F(n) = F(n-1)+F(n-2)（n>=3） 状态转移方程（核心）
    
    F(8)、F(9)是F(10)的最优子结构

代码实现：

/**
    * @param {number} n
    * @return {number}
    */
    const climbStairs = function(n) {
        // 初始化状态数组
        const f = [];
        // 初始化已知值
        f[1] = 1;
        f[2] = 2;
        // 动态更新每一层楼梯对应的结果
        for(let i = 3;i <= n;i++){
            f[i] = f[i-2] + f[i-1];
        }
        // 返回目标值
        return f[n];
    };

再优化一下：

时间复杂度：O(N)  
空间复杂度：O(1)

const climbStairs= function(n) {
        if(n<1) return 0;
        if(n==1) return 1;
        if(n==2) return 2; 
        let a = 1;
        let b = 2;
        let temp = 0;
        for(let i = 3;i<=n;i++){
                temp = a+b;
                a = b;
                b = temp;
            }
        return temp;
    }

[本文链接https://blog.csdn.net/qq\_39903567/article/details/115833964][https_blog.csdn.net_qq_39903567_article_details_115833964]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTAzNTY3_size_16_color_FFFFFF_t_70]: /images/20221022/dbbbfac7d2f24d9bbec889147b98a88a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTAzNTY3_size_16_color_FFFFFF_t_70 1]: /images/20221022/2deb7a227e3c486396220b8aa57d234e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTAzNTY3_size_16_color_FFFFFF_t_70 2]: /images/20221022/c72f4e97817143c69fd665be9d6c4b5b.png
[https_blog.csdn.net_qq_39903567_article_details_115833964]: https://blog.csdn.net/qq_39903567/article/details/115833964