動態程式設計

動態程式設計是對 Brute Force 的改進,請參閱此示例以瞭解如何從 Brute Force 獲得動態程式設計解決方案。

動態程式設計解決方案有兩個主要要求:

  1. 重疊的問題

  2. 最優子結構

重疊子問題意味著問題的較小版本的結果被重複使用多次,以便得出原始問題的解決方案

最優子結構意味著有一種從子問題中計算問題的方法。

動態程式設計解決方案有兩個主要元件,即 StateTransition

是指原問題的一個子問題。

過渡是解決問題的方法是根據它的子問題

動態程式設計解決方案所需的時間可以計算為 No. of States * Transition Time。因此,如果解決方案具有 N^2 狀態並且轉換是 O(N),那麼解決方案將花費大約時間 4。