很多復雜的問題需要使用動態規劃，使用動態規劃和分治法不同之處在于，分治將大問題分解為不重疊的小問題，而動態規劃應用于子問題重疊的情況。在處理復雜問題時要時刻有這根筋，如果只是簡單的遍歷這樣算法的復雜度就變為了指數級別。

動態規劃問題的步驟：

1、刻畫最優解

2、遞歸定義最優解

3、采用自底向上的方法來計算最優解。（如果遞歸，同樣是指數級別）

4、利用計算信息構造最優解。

輔助空間一般是一張表。

一些用到動態規劃的例子：鋼條分割、矩陣鏈相乘、最大公共子序列、最優二叉搜索樹等。

具體就不說了，要學會寫偽代碼~~~~(>_<)~~~~

總結

以上是生活随笔為你收集整理的面试题总结14 动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。