动态规划（一）：爬楼梯
题目
一个
阶的楼梯，每次能走 1～2 阶，问走到
阶一共多少种走法
分析
因为每次能走 1～2 阶，所以第
阶的前一个状态可以是第
阶，或第
阶
，且只有这两种情况。
解答
以
表示到达第
阶的所有走法个数，当
时，则有：
当
时，处于原地，因为步长为 1 ~ 2 阶，不能有前进之后再后退的情况，所以只能有当前一种方式，所以
当
时，只能选择步长为 1 一种方式，所以
根据此推到公式可以有如下解法。
递归形式
def climbingStairs(n):
if n == 0 or n == 1:
return 1
return climbingStairs(n-1) + climbingStairs(n-2)递归形式的时间复杂度为
，空间复杂度为
。
时间复杂度参考斐波那契数列的时间复杂度 Time complexity of recursive Fibonacci program， 因为递归栈数最深为
层，所以空间复杂度为
。
迭代形式
递归形式算法的时间复杂度呈指数级增长，所以这种算法较为不现实。观察递推关系式：
可以发现，每个阶梯数的函数值，只与其前两项的函数值有关，所以不妨由低到高进行推导。
def climbingStairs(n):
a, b, i = 1, 1, 2
while i <= n:
a, b, i = b, a + b, i + 1
return b以
表示
，迭代更新
的值，即可得出最后的结果。时间复杂度为
，空间复杂度为
。
矩阵形式
根据递推关系式，对二阶差分方程构造矩阵：
![\begin{align} \left [ \begin{array} {cc} F(N)\\F(N-1) \end{array}\right ] & = \left [ \begin{array} {cc} F(N-1)+F(N-2)\\ F(N-1) \end{array}\right ] \\ & =\left [ \begin{array} {cc} 1&1\\1&0 \end{array}\right ] * \left [ \begin{array} {cc} F(N-1)\\F(N-2) \end{array}\right ] \end{align}](https://ask.qcloudimg.com/http-save/yehe-3177482/91ru3bhg6a.svg)
根据
![\left [ \begin{array} {cc} F(N)\\F(N-1) \end{array}\right ]](https://ask.qcloudimg.com/http-save/yehe-3177482/e0lbq7kvcy.svg)
的递推关系式， 可得：
![\begin{align} \left [ \begin{array} {cc} F(N)\\F(N-1) \end{array}\right ] & = \left [ \begin{array} {cc} 1&1\\1&0 \end{array}\right ]^{N-1} * \left [ \begin{array} {cc} F(1)\\F(0) \end{array}\right ] \end{align}](https://ask.qcloudimg.com/http-save/yehe-3177482/xy2ta6trsb.svg)
import numpy as np
import math
def climbingStairs_matrix(n):
unit = np.array([[1, 1], [1, 0]])
target, result = n - 1, np.identity(2, int) # target means the total index
while target > 1:
index, tmp = 1, unit
times = int(math.log2(target)) # the iterations times
while index <= times:
tmp, index = np.dot(tmp, tmp), index + 1
result = np.dot(tmp, result)
target = target - 2 ** times
result = np.dot(unit, result) if target == 1 else result
result = np.dot(result, np.array([[1], [1]]))
return result[0][0]- 最好情况下
以求
值为例，若
，则有如下分析：
若已知
，因为
，则只需要一次计算即可;
若已知
，因为
，则得出
值需要两次计算，首先计算出
，然后计算出
; ... ... ... 若已知
，则计算出
需要
次计算，即计算
值的时间复杂度为
即最好情况下矩阵运算的时间复杂度为
，空间复杂度为
。
- 最坏情况下
以求
值为例，若
，则有：
由最好情况分析结论知，
的计算次数为
。若已知
，则得出
的值需要
次计算。
递推有：
由最好情况分析结论知，
的计算次数为
。若已知
，则得出
的值需要
次计算。 ... ... ...
则得出
的值需要
次计算。
即最坏情况下矩阵运算的时间复杂度为
，空间复杂度为
。
若使用逆矩阵，则逆矩阵的个数
存在同样问题，所以此处不涉及逆矩阵运算。
保留中间状态的矩阵形式
观察以上矩阵形式的代码可知，非最优场景下的计算过程存在重复运算，虽然通过对数形式降低了重复的次数，但依然存在计算能力的浪费。针对该情况，申请空间保留中间计算状态。
def climbingStairs_matrix(n):
unit = np.array([[1, 1], [1, 0]]) # M represents the unit matrix
arr, target, result = [unit], n - 1, np.identity(2, int) # target means the total index
while target > 1:
index, tmp = 1, unit
times = int(math.log2(target)) # the iterations times
if times >= len(arr):
while index <= times:
tmp, index = np.dot(tmp, tmp), index + 1
arr.append(tmp)
else:
tmp = arr[times]
result = np.dot(tmp, result)
target = target - 2 ** times
result = np.dot(unit, result) if target == 1 else result
result = np.dot(result, np.array([[1], [1]]))
return result[0][0]代码中增加
数组保存中间的计算状态，其中
![arr[i]](https://ask.qcloudimg.com/http-save/yehe-3177482/tr22ib2i4a.svg)
表示
的值。该形式的矩阵运算时间复杂度为
，空间复杂度为
。
拓展形式
当步长调整为 1～
阶时，问走到
阶一共多少种走法
递归形式
def climbingStairs(n, m):
if n == 0:
return 1
stepSize, result = n if m >= n else m, 0
for i in range(1, stepSize + 1):
result += climbingStairs4(n - i, m)
return result递归关系式由
更新为
，增加步长
与
的大小关系判断。
迭代形式
def climbingStairs(n, m):
if n <= 1 or m == 1:
return 1
stepSize = n if m >= n else m
arr = [0] * stepSize
arr[0], arr[1], index, tmp = 1, 1, 2, 1
while index <= n:
if index > stepSize:
tmp, arr[index % stepSize] = arr[index % stepSize], arr[(index - 1) % stepSize] * 2 - tmp
else:
arr[index % stepSize] = arr[(index - 1) % stepSize] * 2
index += 1
return arr[(index - 1) % stepSize]时间复杂度与步长为 1 ~ 2 时相同，为
。因为需要申请空间存储中间状态数据，所以空间复杂度为
，其中
表示最大步长。