動態程式設計

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

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

1. 重疊的問題

2. 最優子結構

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

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

動態程式設計解決方案有兩個主要元件，即 State 和 Transition

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

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

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