题目

矩阵形式

根据递推关系式，对二阶差分方程构造矩阵：

根据 的递推关系式， 可得：

import numpy as npimport mathdef 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]

代码中增加 数组保存中间的计算状态，其中 表示 的值。该形式的矩阵运算时间复杂度为 ，空间复杂度为 。

拓展形式

递归形式

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 时相同，为 。因为需要申请空间存储中间状态数据，所以空间复杂度为 ，其中 表示最大步长。

作者：zhipingChen
链接：https://www.jianshu.com/p/c93ed24932c2