爬楼梯 斐波那契数列 动态规划
一、题目
https://leetcode.cn/problems/climbing-stairs/
这是一道简单题，核心是找到爬楼梯的规律，通过题目不难看出是斐波那契数列（每个数都是前两个数之和），有目标答案实现解体过程并不难。
二、思路推导
因此写本文的目的不在于如何解这道题，在于捋清解题思路，为什么是斐波那契数列。
本题给的条件有两个，1、一步爬一个台阶，2、一次步两个台阶；
那么 a 只爬一阶时，只有一种方法，1阶，可以写成：
输入：n = 1
解释：有一种方法可以爬到楼顶。
1-1. 1 阶
b 只爬两阶时：
输入：n = 2
解释：有两种方法可以爬到楼顶。
2-1. 1 阶 + 1 阶
2-2. 2 阶
根据 a 的基础找规律，发现2-1是1-1的基础上爬一阶（条件1），而2-2则是一步爬两阶（条件2），和 a 没关系。
c 只爬三阶时：
输入：n = 3
解释：有三种方法可以爬到楼顶。
3-1. 1 阶 + 1 阶 + 1 阶
3-2. 1 阶 + 2 阶
3-3. 2 阶 + 1 阶
3-1、3-2是在2-1、2-2的基础上爬一阶（条件1），3-3是一步爬两阶，再爬一阶，不太能看得出和 ab 有什么关系，继续推。
d 只爬四阶时：
输入：n = 4
解释：有五种方法可以爬到楼顶。
4-1. 1 阶 + 1 阶 + 1 阶 + 1 阶
4-2. 1 阶 + 1 阶 + 2 阶
4-3. 1 阶 + 2 阶 + 1 阶
4-4. 2 阶 + 1 阶 + 1 阶
4-5. 2 阶 + 2 阶
很显然可以得出，4-1～4-3是3-1～3-3基础上再爬一阶（条件1），这个规律就很明显了，每一步都是上一步再爬一阶（条件1）。
4-4、4-5和 c 没什么关系，再往上看b，可以明显看出，4-4、4-5是2-1、2-2的基础上一步爬两阶（条件二）。
规律初步就找出来了，一次爬N阶楼梯，一次爬N-1阶楼梯再爬一阶（条件1），一次爬N-2阶楼梯再一步爬两阶（条件2）。
验证一下， e 只爬五阶时：
输入：n = 5
解释：有八种方法可以爬到楼顶。
5-1. 1 阶 + 1 阶 + 1 阶 + 1 阶 + 1 阶
5-2. 1 阶 + 1 阶 + 1 阶 + 2 阶
5-3. 1 阶 + 1 阶 + 2 阶 + 1 阶
5-4. 1 阶 + 2 阶 + 1 阶 + 1 阶
5-5. 1 阶 + 2 阶 + 2 阶
5-6. 2 阶 + 1 阶 + 1 阶 + 1 阶
5-7. 2 阶 + 1 阶 + 2 阶
5-8. 2 阶 + 2 阶 + 1 阶
爬五阶时，爬四阶（d）再爬一阶（条件1）：5-1～5-5是4-1～4-5的基础上再爬一阶（条件1）✅
爬三阶（c）再一步爬两阶（条件2）：5-6～5-8是3-1～3-3的基础上再一步爬两阶（条件2）✅
规律得证。
三、多条件延伸
再延展一下，在条件一、二的基础上增加 条件3：一步爬三阶。
计算一次爬N阶楼梯的规律也很好推算出来，一次爬N阶楼梯，一次爬N-1阶楼梯再爬一阶（条件1），一次爬N-2阶楼梯再一步爬两阶（条件2），一次爬N-3阶楼梯再一步爬三阶（条件3）。
所以这类题的基础是最小子元素，即给了几个条件，这类题的规律是斐波那契数列及其变种。
而思路是当前结果只和前几个步骤，有规律但固定的发生关联。
解题也很容易：
-
设置一个数组，该数组的每个值都是前几个值运算得出的；
- 确定和确切前几步发生关联，推导出公式；
- 确定最小子元素（每步都含以前没有的条件，不可递推运算出来）；
- 遍历。
四、动态规划
与递归不同（之和前一步有关联），和前几步发生关联的叫动态规划 Dynamic Programing，动态规划的要点就是如上四步。
动态规划是运筹学的一个分支，是求解决策过程最优化的过程。在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。