動態(tài)規(guī)劃（一）：爬樓梯

題目

一個 $N$ 階的樓梯谴咸，每次能走 1～2 階净刮，問走到 $N$ 階一共多少種走法

分析

因為每次能走 1～2 階谓晌，所以第 $N$ 階的前一個狀態(tài)可以是第 $N-1$ 階具温，或第 $N-2$ 階 $(N\ge2)$ 蚕涤，且只有這兩種情況。

解答

以 $F(N)$ 表示到達第 $N$ 階的所有走法個數铣猩，當 $N\ge2$ 時揖铜，則有： $F(N)=F(N-1)+F(N-2)$

當 $N=0$ 時，處于原地达皿，因為步長為 1 ~ 2 階天吓，不能有前進之后再后退的情況贿肩，所以只能有當前一種方式，所以 $F(0)=1$

當 $N=1$ 時龄寞，只能選擇步長為 1 一種方式汰规，所以 $F(1)=1$

根據此推到公式可以有如下解法。

遞歸形式

def climbingStairs(n):
    if n == 0 or n == 1:
        return 1
    return climbingStairs(n-1) + climbingStairs(n-2)

遞歸形式的時間復雜度為 $O((\frac{1+\sqrt(5)}2)^N)$ 物邑，空間復雜度為 $O(N)$ 溜哮。

時間復雜度參考斐波那契數列的時間復雜度 Time complexity of recursive Fibonacci program，
因為遞歸棧數最深為 $N$ 層色解，所以空間復雜度為 $O(N)$ 茬射。

迭代形式

遞歸形式算法的時間復雜度呈指數級增長，所以這種算法較為不現實冒签。觀察遞推關系式：

$F(N)=F(N-1)+F(N-2)$

可以發(fā)現在抛，每個階梯數的函數值，只與其前兩項的函數值有關萧恕，所以不妨由低到高進行推導刚梭。

def climbingStairs(n):
    a, b, i = 1, 1, 2
    while i <= n:
        a, b, i = b, a + b, i + 1
    return b

以 $a, b$ 表示 $F(N-2), F(N-1)$ ，迭代更新 $a, b$ 的值票唆，即可得出最后的結果朴读。時間復雜度為 $O(N)$ ，空間復雜度為 $O(1)$ 走趋。

矩陣形式

根據遞推關系式衅金，對二階差分方程構造矩陣：

$\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}$

根據 $\left [ \begin{array} {cc} F(N)\\F(N-1) \end{array}\right ]$ 的遞推關系式，可得：

$\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}$

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]

最好情況下

以求 $M^N$ 值為例簿煌，若 $2^k=N$ 氮唯，則有如下分析：

若已知 $M^{\frac N2}$ ，因為 $M^N=M^{\frac N2} * M^{\frac N2}$ 姨伟，則只需要一次計算即可;

若已知 $M^{\frac N4}$ 惩琉，因為 $M^{\frac N2}=M^{\frac N4} * M^{\frac N4}$ ，則得出 $M^N$ 值需要兩次計算夺荒，首先計算出 $M^{\frac N2}$ 瞒渠，然后計算出 $M^N$ ;
...
...
...
若已知 $M$ ，則計算出 $M^N$ 需要 $k$ 次計算技扼，即計算 $M^N$ 值的時間復雜度為 $O(log_2N)$

即最好情況下矩陣運算的時間復雜度為 $O(log_2N)$ 伍玖，空間復雜度為 $O(1)$ 。

最壞情況下

以求 $M^N$ 值為例剿吻，若 $2^k-1=N$ 窍箍，則有：

$M^N=M^{2^{k-1}} * M^{2^{k-1}-1}$

由最好情況分析結論知， $M^{2^{k-1}}$ 的計算次數為 $k-1$ 。若已知 $M^{2^{k-1}-1}$ 仔燕，則得出 $M^N$ 的值需要 $(k-1)+1$ 次計算造垛。

遞推有：

$M^{2^{k-1}-1}=M^{2^{k-2}} * M^{2^{k-2}-1}$

由最好情況分析結論知， $M^{2^{k-2}}$ 的計算次數為 $k-2$ 晰搀。若已知 $M^{2^{k-2}-1}$ 五辽，則得出 $M^N$ 的值需要 $(k-1)+1+(k-2)+1$ 次計算。
...
...
...

$M^3=M^2*M$

則得出 $M^N$ 的值需要 $(k-1)+1+(k-2)+1...+(1)+1=\frac {k^2}2+\frac k2-1$ 次計算外恕。

即最壞情況下矩陣運算的時間復雜度為 $O((log_2N)^2)$ 杆逗，空間復雜度為 $O(1)$ 。

若使用逆矩陣鳞疲，則逆矩陣的個數 $N$ 存在同樣問題罪郊，所以此處不涉及逆矩陣運算。

保留中間狀態(tài)的矩陣形式

觀察以上矩陣形式的代碼可知尚洽，非最優(yōu)場景下的計算過程存在重復運算悔橄，雖然通過對數形式降低了重復的次數，但依然存在計算能力的浪費腺毫。針對該情況癣疟，申請空間保留中間計算狀態(tài)。

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$ 數組保存中間的計算狀態(tài)潮酒，其中 $arr[i]$ 表示 $unit^{2^i}$ 的值睛挚。該形式的矩陣運算時間復雜度為 $O(log_2N)$ ，空間復雜度為 $O(log_2N)$ 急黎。

拓展形式

當步長調整為 1～ $M$ 階時扎狱，問走到 $N$ 階一共多少種走法

遞歸形式

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

遞歸關系式由 $F(N)=F(N-1)+F(N-2)$ 更新為 $F(N)=F(N-1)+F(N-2)+...+F(N-M)$ ，增加步長 $M$ 與 $N$ 的大小關系判斷勃教。

迭代形式

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 時相同淤击，為 $O(N)$ 。因為需要申請空間存儲中間狀態(tài)數據荣回，所以空間復雜度為 $O(M)$ 遭贸，其中 $M$ 表示最大步長。