怎麼列動態規劃遞推方程？

01-14

看到問題，自己總是想不出來方程，但是看到別人的方程又覺得簡單而巧妙。。該怎麼思考尋找方程這一過程？？？？

第一步，設計狀態。狀態用哪些參數來表示，各參數表示什麼意義，狀態本身是否完整唯一，不同狀態間是否無依賴。

第二步，設計函數意義，最優化函數代表的是什麼意義？如果是解那麼是否涵蓋所有情況？如果不是解是否能夠通過某種簡單計算用最優化結果求出解求出解。

第三步，設計轉移。狀態間轉移有什麼條件？是否覆蓋題設所有情況？轉移是否拓撲有序（理論上前兩步分析得到確定結果必定是滿足的）

第四步，可否優化？可否合併某些狀態？可否合併某些轉移？有無單調性？可否用某些數據結構（BST之類）優化？

第五步，確定實現方案。基本上就是寫代碼。

啊當然如果是ACM競賽的話還有個第0步，看數據規模湊時間複雜度估算可承受範圍和狀態、轉移維數以及是否存在優化措施……

設計狀態很關鍵，設計的狀態要足矣表示當前情況，然後可以進行轉移。

有了狀態，就思考如何轉移過去了，想多了很多轉移都是非常顯然的。

我的經驗是，先寫遞歸，這時候遞歸的參數就是矩陣的維度，然後就可以建立遞推關係了，遞歸是第一步，dp是其優化的第二步。

做他一百題。

首先，你得能看出來這道題考的是動態規劃。

你知道看到問題通過寫代碼來解決問題實際上其中有很重要的一步就是建模。那麼怎麼才能看出來這考的是動態規劃呢？動態規劃作為一種經典的思想是有很多經典的例題作為支撐的，例如初學者最先接觸的最長不下降子序列及其變式，還有各種背包問題及其變式等等。

所以，建議多打一打這些「經典」，熟能生巧，你會發現解決問題的關鍵是列狀態轉移方程。

這一類題的特點是各個確定數據狀態條件對應確定的答案值（類似函數中自變數與因變數的對應關係），而答案值是可由更小規模的數據狀態的答案值推出來（局部最優解可求得全局最優解），即具有遞推關係。

而核心代碼往往是多重嵌套的for循環，操作的數據結構往往是多維數組（此時數組下標可以看成是自變數，數組元素存入的值是因變數即最優值，自變數和因變數組成了一個「狀態」），循環變數往往用於控制操作的數組下標的變化（注意不一定循環變數一定要遞增變化，有時也可以遞減），循環體往往是通過已經求得的相對小規模局部最優解對當前狀態的解進行優化（類似於單源最短路徑演算法中的鬆弛操作）。

動態規劃也算是複雜的遞推了。重要的是動手實踐，世上無難事，只怕有心人。

多做題，dp是acmer必備技能之一，你可以去acmer常去的online judge上看看DP問題，有很多，一般dp要滿足無後效性和最優子結構，多做做題邊漸漸能找到感覺

這個問題要理論結合實際，講道理還要配例題。太麻煩..

做他100題確實可以。