动态规划入门（记忆化搜索）——爬楼梯（Leetcode 70题）

动态规划

动态规划是通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，换而言之：这个问题的解决可以通过解决许多个小的子问题来构建，而这些子问题会重复出现。

记忆化搜索

入门的动态规划的基础是记忆化搜索，或者说记忆化搜索是动态规划的一种，而动态规划是一种更广泛的概念，它包括了记忆化搜索记。忆化搜索是动态规划在递归算法中的一种实现方式。动态规划可以不使用递归，而记忆化搜索通常与递归结合使用。两种方法都是在通过存储中间结果来避免重复计算，从而提高算法的效率。

值得注意的是：

记忆化搜索并不是万能的，多数题目都要通过递归来实现，因此在时间复杂度上可能并不优秀，尽管可以通过一些数据结构来优化时间和空间复杂度，但是还是应该值得我们去注意。

题目 

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/climbing-stairs

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

分析 （递归思想）

 我们每次都只能爬1或2个台阶，因此我们倒过来看这道题目，我们最后上到楼顶前只能有两种情况：

1、走1个台阶，也就是我们需要先得到0——n-1级台阶的方法

2、走2个台阶，也就是我们需要先得到0——n-2级台阶的方法

这样我们就把问题缩小成：

f[n]=f[n−1]+f[n−2]

代码实现：

class Solution {
    public int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        return climbStairs(n-1)+climbStairs(n-2);
    }
}

但是很明显的是这样做的时间复杂度为O(2^n)，很明显会超时。我们也可以发现整个递归中有大量重复递归调用，例如：

在计算发f[7]时我们的计算过程为：f[7]=f[6]+f[5]  f[6]=f[5]+f[4]……先看前两个式子那么我们是不是就调用了两次f[5]这样的重复是很多的，这也加大了时间复杂度，那么我们可以通过记录每个f[i]的返回值来减少重复调用，也就是递归 + 记录返回值 = 记忆化搜索，这便是记忆化搜索那我们接着来看看记忆化搜索的办法。

记忆化搜索解题

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

通过记忆化搜索我们的时间复杂度成功降到了 O(n)。

优化

 这里我们创建了一个数组来存储f[i]的返回值，因此空间复杂度为O(n)，那么当n足够大时便会出现内存溢出，因此我们还可以优化。通过观察不难发现发现一旦算出 f[i]，那么  除了f[i−1]和f[i−2]以外的值我们都不用了，因此我们每次只需要保留f[i−1]和f[i−2]就可以了。

class Solution {
    public int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        int a=1;
        int b=2;
        for(int i=3;i<=n;i++){
            int c=a+b;
            a=b;
            b=c;
        }
        return b;
    }
}