题目

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

分析

这题，如果做过斐波那契数列的话，一眼就看得出一模一样，但是我这篇文章的目的不是单纯的为了解题，还为了练习我们用动态规划解题的思想。

1、动态规划的本质是什么？

在我看来求解动态规划类型的问题的本质就是穷举。

只不过，因为有重叠子问题，所以可以把子问题用一维数组或者二位数组缓存起来，求解过程中就不用去多做一遍了。

2、主要难题点？

找到状态转移方程。

如果我们能够找到状态转移方程，那么很容易就可以根据递归暴力破解。也可以把每个状态对应的结果缓存起来，提高效率（动态规划）。

3、怎么找到状态转移方程？

我们知道，能够用动态规划解的题目，都有两个特点

1、最优子结构
2、重叠子问题

如果一个问题步满足上面两个条件，那就不能用动态规划来解了。

找状态转移方程，首先要找到【状态】是啥，状态就是原问题和子问题中会变化的变量，在这个爬楼梯的例子中，原问题和子问题中会变化的两就是n（阶梯数）；
当我们找到状态后，我们需要找到导致状态变化的行为，也就是【选择】，在爬楼梯的例子中，导致状态变化的行为就是爬楼梯是爬1还是爬2；
然后我们可以找到我们的【dp函数】，通常输入是跟状态有关的，然后输出是结果，这个例子中输入是阶梯数n，输出是爬楼梯的方案数；
既然是递归的方式可以解决的，那我们还需要找到基准值，也就是当状态变化到最小的时候，可以直接知道结果的dp函数结果，这里是当n=1时，dp(n)=1;当n=2时，dp(n)=2;

然后我们根据题意，就很容易列出【状态转移方程】,在这个问题里，用户通过什么选择达到了状态n，这里有两种选择，爬1还是爬2，所以总方案数就是dp(n-1)+dp(n-2)

dp(n)=dp(n-1)+dp(n-2):dp(1)=1;dp(2)=2

这里直接这样列出来了，没有写成数学公式。

解题

1、粗暴递归

我们可以根据状态转移方程很粗暴的用递归的方法求解

public int op(int n) {
        if(n==1) {
            return 1;
        }
        if(n==2) {
            return 2;
        }
        //1、当前阶梯是上一阶梯爬一步上来的
        int one = op(n-1);
        //2、当前阶梯是上一阶梯爬两步上来的
        int two = op(n-2);
        return one+two;
    }

当然这样子效率肯定机器低下哎，毕竟我们这个状态转移方程存在有很多重叠子问题，如果化成一个树来分析会发现假设计算dp(9),那么左边的树是dp(8),右边的树是dp(6)，都含有重叠子问题比如dp(5),随着n的增大，时间复杂度指数级上升O(2^n),所以我们需要用动态规划的方法，把子问题的解保存在一张dp表中，可以是一维数组或者二维数组甚至是n维数组，这个要看你的状态转移方程来定，比如这里就用一维数组就可以了。

2、动态规划的方式解决

public int climbStairs(int n) {
        //dp函数是一个以为数组，存放的是阶梯n对应的方法数目
        int[] dp = new int[n];
        if(n>=1) {
            dp[0]=1;
        }
        if(n>=2) {
            dp[1]=2;
        }
        for(int i=2;i<n;i++) {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n-1];
    }

其实如果对于这个问题，计算的值只会跟前面两个值有关，所以这里用一个大小为2的数组或者两个变量缓存子问题的解即可。

public int climbStairs2(int n) {
        //dp函数是一个以为数组，存放的是阶梯n对应的方法数目
        if(n==1) {
            return 1;
        }
        if(n==2) {
            return 2;
        }
        int one=1;
        int two=2;
        int now=0;
        for(int i=2;i<n;i++) {
            now=one+two;
            one=two;
            two=now;
        }
        return now;
    }

总结

动态规划问题的解法

1、判断问题是否具有【最优子结构】，也就是子问题和子问题之间不会互相影响
2、判断问题是否具有【重叠子问题】，毕竟动态规划的本质就是穷举，只不过把子问题的解缓存了起来而已
3、确定【状态】，也就是原问题和子问题中会变化的变量，比如零钱找零问题的状态就是金额，爬楼梯问题的状态就是楼梯数目
4、确定【选择】，也就是导致状态变化的量，比如选择爬1还是爬2
5、确定【状态函数】，一般参数会包含状态，结果为目标值
6、确定【基准值】，也就是状态为0或者1或者2的时候，函数的值
7、列出【状态转移方程】
8、编码解决【缓存子问题结果】

其实网上看到一个伪代码的例子总结很棒

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

参考：https://leetcode-cn.com/problems/fibonacci-number/solution/dong-tai-gui-hua-tao-lu-xiang-jie-by-labuladong/