算法學習筆記（八） 動态規劃的一般求解方法

1 一個問題：換零錢方式的統計

SICP 第一章 1.2.2 樹形遞歸中，有這麼一問題：給了半美元，四分之中的一個美元。10美分，5美分和1美分的硬币。将1美元換成零錢，一共同擁有多少種不同方式？更一般的問題是，給定了随意數量的現金，我們能寫一個程式，計算出全部換零錢方式的種數嗎？

2 動态規劃的基本模型

動态規劃（Dynamic programming，DP），是研究一類最優化問題的方法，通過把原問題分解為相對簡單的子問題的方式求解複雜問題。動态規劃處理的也就是是多階段決策最優化問題，這一類問題可将過程分成若幹個互相聯系的階段，在每一階段都作出決策，進而使整個過程達到最好的結果。

是以各個階段決策的選取不能随意确定，它依賴于目前面臨的狀态。又影響以後的發展。當各個階段決策确定後，就組成一個決策序列，進而也就确定了整個過程的一條活動路線。這樣的把一個問題看做是一個前後關聯具有鍊狀結構的多階段過程稱為多階段決策過程。

動态規劃著名的應用執行個體有：求解最短路徑問題，背包問題，項目管理，網絡流優化等。動态規劃的基本模型例如以下：

1. 确定問題的決策對象
2. 對決策過程劃分階段
3. 對各階段确定狀态變量
4. 依據狀态變量确定費用函數和目标函數
5. 建立各階段狀态變量的轉移過程。确定狀态轉移方程

3 使用動态規劃的一般前提

3.1 滿足動态規劃的最優化原理

作為整個過程的最優政策具有例如以下性質：不管過去的狀态和決策怎樣，對前面的決策所形成的目前狀态而言，餘下的諸決策必須構成最優政策。

通俗了解就是子問題的局部最優将導緻整個問題的全局最優，即問題具有最優子結構的性質，也就是說一個問題的最優解僅僅取決于其子問題的最優解，非最優解對問題的求解沒有影響。

3.2 滿足動态規劃的無後效性原則

所謂無後效性原則。指的是這樣一種性質：某階段的狀态一旦确定，則此後過程的演變不再受此前各狀态及決策的影響。也就是說，“未來與過去無關”，目前的狀态是此前曆史的一個完整總結，此前的曆史僅僅能通過目前的狀态去影響過程未來的演變。

詳細地說，假設一個問題被劃分各個階段之後，階段 I 中的狀态僅僅能由階段 I+1 中的狀态通過狀态轉移方程得來，與其它狀态沒有關系，特别是與未發生的狀态沒有關系，這就是無後效性。從圖論的角度去考慮。假設把這個問題中的狀态定義成圖中的頂點，兩個狀态之間的轉移定義為邊，轉移過程中的權值增量定義為邊的權值，則構成一個有向無環權重圖，是以，這個圖能夠進行“拓撲排序”，至少能夠按他們拓撲排序的順序去劃分階段。

4 動态規劃設計方法

4.1 一般方法

一般由初始狀态開始。通過對中間階段決策的選擇，達到結束狀态。這些決策形成了一個決策序列，同一時候确定了完畢整個過程的一條活動路線。步驟為：

1. 劃分階段：依照問題的時間或空間特征，把問題分為若幹個階段。在劃分階段時。注意劃分後的階段一定要是有序的或者是可排序的。否則問題就無法求解。
2. 确定狀态和狀态變量：将問題發展到各個階段時所處于的各種客觀情況用不同的狀态表示出來。當然，狀态的選擇要滿足無後效性。
3. 确定決策并寫出狀态轉移方程：由于決策和狀态轉移有着天然的聯系。狀态轉移就是依據上一階段的狀态和決策來導出本階段的狀态。是以假設确定了決策，狀态轉移方程也就可寫出。但其實經常是反過來做。依據相鄰兩段各狀态之間的關系來确定決策。
4. 尋找邊界條件：給出的狀态轉移方程是一個遞推式，須要一個遞推的終止條件或邊界條件。
5. 程式設計實作：動态規劃的主要難點在于理論上的設計。一旦設計完畢，實作部分就會很easy。

4.2 逆向推導

逆向思維法是指從問題目标狀态出發倒推回初始狀态或邊界狀态的思維方法。假設原問題能夠分解成幾個本質同樣、規模較小的問題，非常自然就會聯想到從逆向思維的角度尋求問題的解決。動态規劃與分治法最大的不同在于分解出來的各個子問題的性質不同：

• 分治法要求各個子問題是獨立的(即不包括公共的子問題)，是以一旦遞歸地求出各個子問題的解後，便可自下而上地将子問題的解合并成原問題的解。假設各子問題是不獨立的，那麼分治法就要做很多不必要的工作，反複地解公共的子問題。
• 動态規劃與分治法的不同之處在于動态規劃同意這些子問題不獨立(即各子問題可包括公共的子問題)，它對每一個子問題僅僅解一次，并将結果儲存起來，避免每次碰到時都要反複計算。這就是動态規劃高效的一個原因。

動态規劃的逆向推導步驟：

1. 分析最優值的結構。刻畫其結構特征；
2. 遞歸地定義最優值；
3. 按自底向上或自頂向下記憶化的方式計算最優值；

4.3 正向推導

正向思維法是指從初始狀态或邊界狀态出發。利用某種規則不斷到達新的狀态，直到問題目标狀态的方法。

動态規劃的正向思維法。正是從已知最優值的初始狀态或邊界狀态開始，依照一定的次序周遊整個狀态空間，遞推出每一個狀态所相應問題的最優值。

在正向思維法中。不再區分原問題和子問題，将動态規劃的過程看成是從狀态到狀态的轉移。将全部的狀态構造出一個狀态空間，并在狀态空間中設想一個狀态網絡。若對兩個狀态i,j，存在決策變量di使t(i，di)=j。則向狀态網絡加入有向邊。

給定己知最優值的初始狀态或邊界狀态，能夠沿著有向邊推廣到未知最優值的新狀态。利用狀态轉移方程得到新狀态的狀态變量的最優值。

我們能夠用這樣的方式周遊整個狀态空間，得到每一個狀态的狀态變量的最優值。

動态規劃的正向推導步驟：

1. 構造狀态網絡；
2. 依據狀态轉移關系和狀态轉移方程建立最優值的遞推計算式：
3. 按階段的先後次序計算每一個狀态的最優值；

動态規劃須要按階段周遊整個狀态空間。是以動态規劃的效率取決于狀态空間的大小和計算每一個狀态最優值的開銷：假設狀态空間的大小是多項式的，那麼應用動态規劃的算法就是多項式時間的；假設狀态空間的大小是指數的，那麼應用動态規劃的算法也是指數時間的。是以，找一個好的狀态劃分對動态規劃的效率是至關重要的。

5 小實驗換零錢問題求解

逆推狀态轉移方程：數量為 a 的錢換成 n 種硬币的不同方式等于：

• 數量為 a 的錢換成除第一種硬币外的 n-1 種硬币(必不包括第一種硬币)的不同方式數目加上，
• 數量為 a-d 的錢(必包括第一種硬币)換成全部硬币種類的不同方式數目。d 為第一種硬币币值

逆推到初始狀态：

• 假設錢為 0 ，說明正好換完成，是一種換零錢方法，
• 假設錢為負數，或者種類已經遞歸到 0 種，則說明沒有正好換完，不是一種換法，傳回0；

還能夠正向推導。打表記錄已經計算出的值。

Python實作

NUM = 0


def count_change(amount, money, kinds):
    ''' 樹形遞歸存在備援'''
    global NUM
    if amount == 0:
        NUM+=1
        return 1
    if amount < 0 or kinds == 0:
        NUM+=1
        return 0
    NUM+=1
    return count_change(amount, money, kinds - 1) + count_change(amount - money[kinds - 1], money, kinds)

def count_dy(amount,money,kinds):
    '''動态規劃，打表記錄已經計算的值'''
    table = [[0 for col in range(kinds)] for row in range(amount+1)]
    table[0] = [1]*kinds
    for i in range(1,amount+1):
        for j in range(kinds):
            # 包括 money[j]
            x = table[i - money[j]][j] if i-money[j] >= 0 else 0
            # 不包括 money[j]
            y = table[i][j-1] if j>=1 else 0
            table[i][j] = x+y
    return table[amount][kinds-1]

if __name__ == '__main__':
    money = [1, 5, 10, 25, 50]
    print(count_change(100, money, len(money)),'time:',NUM)
    print(count_dy(100, money, len(money)),'time:',100*len(money))

'''
292 time: 15499
292 time: 500
'''      

SICP中的Scheme實作(Racket)