JavaScript中的動態規劃

動態規劃將問題分解成越來越小的子問題。這些子問題並不是獨立解決的。相反，這些較小子問題的結果會被記住並用於類似或重疊的子問題。

動態規劃用於解決可以分解成類似子問題的問題，以便可以重用其結果。通常，這些演算法用於最佳化。在解決手頭的子問題之前，動態演算法會嘗試檢查先前解決的子問題的結果。子問題的解決方案被組合起來以實現最佳解決方案。

要使用動態規劃解決問題，

• 問題應該能夠分解成較小的重疊子問題。
• 可以透過使用較小子問題的最優解來獲得最優解。
• 動態演算法使用記憶化。

動態規劃問題可以使用兩種方法解決 -

• 自底向上動態規劃：在這種方法中，我們首先分析問題並檢視解決子問題的順序。我們從解決瑣碎的子問題開始，逐步構建到給定的問題。

• 自頂向下動態規劃：在這種方法中，我們從分解給定問題開始解決它。如果您發現某個給定的子問題已經被解決，則只需返回儲存的解決方案。

Samual Sam

更新於: 2019年7月30日

2K+ 閱讀量

開啟你的職業生涯

透過完成課程獲得認證

開始學習