Leetcode 爬楼梯 （Python解法）

问题定义：

 

算法思路：

本题是动态规划的一个经典实例。

解动态规划问题的步骤：

1.找出状态转移方程

2.设计自顶而下的递归算法 （Top-down approach）

3.改写成自底而上的迭代算法（Bottom-up approach）

比较熟练或者问题比较简单时可以跳过第二步。

在本题中，通过举例可以推出状态转移方程。首先要注意到每一步只能走一个阶梯或者两个阶梯。假如有n个阶梯，可以分成两部分来走，先走一个阶梯，再走剩下的n-1个阶梯，或者先走两个阶梯，再走剩下的n-2个阶梯，有两种组合方式。对于剩下的n-1或者n-2个阶梯怎么走呢？也是相同的处理方法，先走一个阶梯或者先走两个阶梯，还是两种组合。一直递归下去即可。

显然，阶数为n时，我们的组合有f(n-1) + f(n-2)种，其中f(n)表示n个阶梯对应的走法。

状态转移方程：f(n) = f(n-1) + f(n-2)

只要递归下去就能解决问题，但动态规划的妙处是计算结果的复用，减少重复的计算。求解每一个n时，我们将计算结果f(n)存起来，就能在后续计算更大的n时调用。比如我们让从i = 1开始迭代，直到i = n，这样每一步都在调用先前计算的结果。

注意到f(n)需要前两项的值，我们要让i从3开始，前两项要初始化（自己写）。

 

代码：