一、题目描述

爬楼梯

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

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

注意：给定 n 是一个正整数。

示例 1：

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

1. 1 阶 + 1 阶
2. 2 阶
   示例 2：

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

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

二、思路分析

• 不知不觉已经刷了不少leetcode了。今天来看看一篇有意思的leetcode–爬楼梯。
• 对于 儿童来说正常最多可以迈出两步台阶至少一步台阶。我们就以这个为前提来生活化本题。
• 既然是迈台阶那么就有一个起点到终点的问题，上学期间经常听老师说做人要脚踏实地、实事求是。我们想要到达终点就得一步一步的往上爬。
• 换句话说终点状态是由开始状态一步一步转变的。既然是一步一步那么正好和我们的动归理论吻合。所以爬楼梯就是动态规划的考点

转移方程

• 动态规划为什么我每次都是先讲转移方程呢？因为他是动归的起点。也是最重要的环节。这里说的起点并不是初始值的意思。而是说他是动态规划整个功能的核心部分。没有他就无法进行运转下去。
• 回到本题我们假设F(x)表示从第一个台阶到第x个台阶的走法个数。从某个台阶我们可迈出一步也可以迈出两步。

• 从上图我们可以得知，F(x)可以由F(x-1)跨一步走过来所以包含了F(x-1);另外也可以有F(x-2)走两步过来。所以得出如下方程

$$
f(x)=f(x-1)+f(x-2)
$$

• 当然这个是x的从1开始的。那么有人会提出疑问，如果x=1那么x-2不就是负数了吗、这里应该解释下这个转移方程。当所处节点是无效状态是按0处理
• 我们可以这样理解，在第二块是他的前一块是第一块且他只有前面一块，那么他只可能是第一块走一步过来的。

初始值

• F(1) = 1 。 这个应该没有问题，我们想进入第一块台阶只有一种可能.还有一点我们需要注意的是F(0) 这种无状态的应该是F(0)=1 。
• 关于F(0) 我们采用倒退理解。从平台直接到第二块台阶可以跨两步这样就是一种方式。而F(2)包含F(0) . 所以F(0)=1

从小到大计算

• 因为F(1) = 1 . 所以F(2) = F(1)+F(0) = 1+1 = 2 。 所以达到第二块台阶一共有两种走法 第一块跨一步+平地跨两步

三、AC 代码

全局保存

public int climbStairs(int n) {
    int[] total = new int[n];
    total[0] = 1;
    for (int i = 1; i < n; i++) {
        if (i > 1) {
            total[i] = total[i - 1] + total[i - 2];
        } else {
            total[i] = total[i - 1] + 1;
        }
    }
    return total[n-1];
}

• 上面是普通的动态规划，借助额外的数组存储每个小问题的结果从而实现大结果
• 在leetcode上提交下结果也是很客观的

局部保存

public int climbStairs(int n) {
    int prepre =1;
    int pre = 1;
    int current = 1;
    for (int i = 1; i < n; i++) {
        current = prepre + pre;
        prepre = pre;
        pre = current;
    }
    return current;
}

• 和上面全局保存不同的是我们只关心最终n台阶的状态，所以我们没有必要保存前面所以台阶的状态。跟我们相关的只有N台阶，N-1台阶，N-2台阶
• 所以我们通过三个变量分别对应N-2,N-1，N这三块台阶的状态。自然最后我们只需要将N台阶状态返回既可以

数学化

• 不知道你有没有发现此题的推倒公式和之前的破解翻译有点像。在或者说你觉得这个推倒公式你似曾相识
• 斐波拉契好像就是这个特性。1,1,2,3,5,8,13..... 。而我们知道斐波拉契的公式也是推倒好了的。
• 如果我们直接通过公式来运行结果的话，在时间复杂度上是不是就是O(1)。

$$
f(n)=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]
$$

• 从O(n)过度到O(1)这在算法上绝对是个优化。毕竟代码是死的人是活的。好多所谓的算法其实在数学界都有很好的总结。只不过计算机拼接高速的计算能力屏蔽了他的短板。所以在算法中经常会使用到数学公式来快速解决问题
• 但是在运行中我们不能说数学公式就一定比我们的算法优秀，因为在公式中有可能产生其他的运算。所以我们要两者结合使用。

四、总结

• 动态规划的确是个好东西，他可以将看似很复杂的东西简单化。
• 动归就是三步骤。掌握它你就可以和程咬金一样吃遍天下

欢迎点赞、关注、收藏哦