1樓：
先提取狀態轉移方程及其邊界條件.
比如在有向無環圖上跑最短路:
defGetDist(x
):ifx
==destination
:return
0dist
=INFINITY
foreach
edge
fromxto
v:dist
=min
(dist
,GetDist(v
)+weight(x
,v))比如求Fib:
def Fib(x) :
if x <= 1 : return 1
return Fib(x-1) + Fib(x-2)
比如求價值最大的切分方案:
def GetValue(l, r) :
ans = value[r - l + 1]
for i in interval [l, r-1] :
ans = max(GetValue(l, i) + GetValue(i+1, r))
return ans
然後構造乙個滿足依賴關係的拓撲序.
對於有向無環圖, 節點 依賴於它的所有後繼節點 . 合法的拓撲序是把原圖所有的邊反向,再做一遍拓撲排序, 得到合法的拓撲序.
對於斐波那契序列, 依賴於 和 , 顯然乙個合法的拓撲序是 順序列舉自然數作為下標. 這保證了 在 和 之後.
對於求價值最大的切分方案, 我們發現依賴關係決定於區間長度. 乙個長度為 的區間依賴於若干個長度小於的區間的結果; 乙個長度為 的區間不依賴於任何乙個長度大於等於的區間的結果. (這句話稍微有點長, 可以好好思考/觀察一下.
) 這樣我們可以得到乙個拓撲序(下面使用符號 表示乙個區間的結果):
把上面每一行的結尾連上下一行的開始, 這樣乙個序列就是乙個合法的拓撲序.
最後按照拓撲序遞推即可, 資料儲存方式隨意.
結束.
2樓：欲言
嗯，我以乙個菜鳥但是過來人身份說一下看法吧。就是你遞迴這部分不清楚怎麼用，那麼我建議你先學分而治之演算法，再學動態規劃。我當初是這麼學的，過渡過去就很自然了。
比如我看到別人說的漢諾塔問題，很經典，但是我沒有記錯的話應該也是分而治之問題。另外我的理解是遞迴在一定程度上和迴圈有點相識。另外祝樓主克服難關，學有所成!
怎樣解決DLL hell問題？
FillZpp 在 Linux 上這不是問題。Linux 共享庫命名規範是 libname.so.x.y.z，其中 x 是主版本號，y 是次版本號，z 是發布版本號。採用 SO NAME 命名機制來記錄共享庫依賴關係，在編譯建立共享庫的時候，用 soname,my soname 來指定建立共享庫的名...
怎樣解決兔子的臭味問題？
為雲g 兩方面 1 源頭上解決，大家說的飲食等 2 解決空氣中的臭味，買乙個空氣淨化器，淨化空氣中的臭味就行，1000多的，放在家裡，不僅可以解決臭味問題，還可以解決細菌 皮屑問題。就在家裡放一點碳粒，作用太小，而且很快就飽和沒有作用。以上完 咕咕咕 我覺得兔會臭，有很大一部分因素是跟他的進食有關，...
怎樣解決房間潮濕的問題？
金招 首先確定潮濕的根源。如果不是在地下室，或者是深圳，海口這些本來就很潮濕的地方。那麼要找到潮濕源，解決源頭最重要。如果本身就住在氣候很潮濕的城市，那麼可以考慮買一台除濕機。除濕機我用下來覺得挺方便的，首先是移動方便，每個房間都可以照顧到。空調雖然也有除濕功能，但根本移動不了。這個是我家除濕機抽出...