如果你搜索動態(tài)規(guī)劃， 那么你能找到的絕大多數(shù)資料都會告訴你，動態(tài)規(guī)劃，是一種把問題拆解為子問題，然后再利用子問題之間的關(guān)系列出狀態(tài)轉(zhuǎn)移方程，最后求把問題變成一個動態(tài)決策求最優(yōu)解的方法。 但是這種說法實在是過于抽象了， 這個描述離實際我們編寫code的距離實在是太遙遠(yuǎn)了， 你一旦去看那些文章那些使用c語言寫的代碼，你就會發(fā)現(xiàn)他們一般都有一個莫名其妙的數(shù)組， 再加上或多或少的幾個莫名其妙的循環(huán)嵌套，整個代碼和上面算法的描述簡直和動態(tài)決策簡直是風(fēng)馬牛不相及 。最后給新人的感覺反而是這個算法很難懂。

問題出在哪呢？ c語言是無法表達(dá)這個算法的。 因為c語言根本不能去描述子問題之間的關(guān)系(Relation)。 而專門解決關(guān)系的語言是存在的， 就是邏輯式編程。不過在邏輯式編程中，也存在大量不同的語言，我們應(yīng)該如何去選擇語言呢。 首先我們可以嘗試先從不同角度來看動態(tài)規(guī)劃。

另一個角度： 圖

如果你上過算法課，你的老師肯定會告訴你，解決DP問題(當(dāng)然，在不考慮使用語言的 情況下)， 是有通用的模板的：所有動態(tài)規(guī)劃問題都可以歸化為一個在有向無環(huán)圖（DAG）中求解最短/最長路徑的問題， 你一定可以找到一種映射關(guān)系，把原問題中的對象映射到圖上的節(jié)點和邊。這種描述聽起來不是那么直觀，為什么一定可以？
回到DP問題的定義，在DP問題中，當(dāng)我們定義了子問題之后， 這些子問題（可以把子問題看成函數(shù)/關(guān)系， 如果你不會Logic Programming的話，就理解成函數(shù)把）在區(qū)不同值的時候是有一定的關(guān)系的， 本質(zhì)他們形成了一個決策狀態(tài)機(jī)，狀態(tài)機(jī)顯然是一個圖。所以這種映射總是存在的。

既然動態(tài)規(guī)劃問題可以看成圖，那為什么一定是DAG呢， 其實也很好理解，如果我們的算法要成立（sound），他一定能找到這個問題的解。如果圖上出現(xiàn)環(huán)，那么最長路徑是不存在的，我們只能求解某些特定的最短路問題，這已經(jīng)和LP定義中的最優(yōu)解矛盾了，因為我們必找不到最大解。從狀態(tài)轉(zhuǎn)移的角度來說，也就是我們會面對不停在一些狀態(tài)打轉(zhuǎn)的問題，我們的決策可能無法在有限步數(shù)內(nèi)結(jié)束，算法不收斂。

從上面的分析我們可以看出，動態(tài)規(guī)劃不但是一個分解子問題后的決策問題，它還蘊含了一個條件，我們的子問題關(guān)系必須是單調(diào)的。這一點如果我們需要證明我們的問題使用動態(tài)規(guī)劃后成立，必須要利用好，這也是這兩天重新翻算法導(dǎo)論我才意識到的。

另一個角度： 格(Lattice)

問題是單調(diào)的?。?br> 也就是說從抽象代數(shù)的角度上來說我們可以把 子問題取不同值時候的狀態(tài)放到一個格上， 如果我們的問題可以用DP解決那么也就是說我們的lattice 必須是有限高度的。在計算機(jī)科學(xué)說，說到格我們會很自然的聯(lián)想到求解不動點的證明也是放在格里去證明的。 這也暗示著我們，如果我們的編程語言語義適合求解不動點，那么也將非常適合描述動態(tài)規(guī)劃問題。 Datalog正好就擁有這種語義。

例子：使用datalog（souffle language）求解DP問題

You have a sequence of n buckets. Each bucket Bi contains three items, where each item has some value and belongs to some category. Multiple items may belong to the same category. Your job is to select exactly one item from each bucket so that the total value of the selected tems is maximized, but such that no two items selected from adjacent buckets belong to the same category. Design an algorithm to determine which item should be selected from each bucket to maximize the total value. If there is no solution, your algorithm should state this.

這是一個典型的DP問題。問題中bucket是自然有序的，因為我們的限制條件是不能從相鄰的位置取， 那么所有的桶一定可以被使用自然數(shù)編號。 所以我們可以使用如下代碼描述輸入。

// item has category ... and weight ... is in bucket ...
.type bucket <: number
.decl InBucket(category: symbol, weight: number, bk: bucket)
InBucket("c1", 200, 1).
InBucket("c1", 300, 1).
InBucket("c3", 150, 1).
InBucket("c1", 300, 2).
InBucket("c2", 200, 2).
InBucket("c3", 200, 2).
InBucket("c1", 500, 3).
InBucket("c3", 400, 3).
InBucket("c3", 200, 3).
InBucket("c2", 400, 4).
InBucket("c1", 200, 4).
InBucket("c1", 500, 4).
InBucket("c3", 200, 5).
InBucket("c1", 300, 5).
InBucket("c2", 400, 5).

桶的順序已經(jīng)形成了一個天然的拓?fù)漤樞?，也就是說我們的node只要是一個桶的，拓?fù)漤樞蚓拖嗤?，在這里我們不妨令圖中的節(jié)點代表桶+當(dāng)前桶中我們選擇的物品的類型和重量。也就是Node的類型是一個元組.
用一下souffle中的類型

.type node = [
    bucket : bucket,
    category : symbol,
    weight: number
]
.decl Node(n: node)
// if same category, we always pick the heaviest
Node([bucket, category, max_weight]) :-
    InBucket(category, _, bucket),
    max_weight = max w : {InBucket(category, w, bucket)}.

接著我們需要用題目中的限制條件，不能有相鄰?fù)暗念愋拖嗤?，來鏈接所有可能的node

.decl Edge(from: node, to: node)
Edge([b, c1, w1], [b+1, c2, w2]) :-
    Node([b, c1, w1]),
    Node([b+1, c2, w2]),
    c1 != c2.
Edge([1, c, w], [1, c, w]) :- Node([1, c, w]).

接下來，datalog最擅長的，求解DAG！
這里是最長路徑

.decl PathLen(from: node, to: node, len: number)
PathLen(f, t, w) :- Edge(f, t), f = t, f = [b, c, w].
PathLen(f, t, w1+w2) :- 
    Edge(f, t), f != t, 
    f = [b1, c1, w1], t = [b2, c2, w2].
PathLen(f, t, l1+l2-w) :- 
    PathLen(f, mid, l1), 
    PathLen(mid, t, l2),
    mid = [b, c, w].
    
.decl LongestPath(n: number)
.output LongestPath
LongestPath(n) :- n = max l : PathLen(_, _, l).

總共40多行，無比清晰。。。。。。