動態規劃法的原理

動態規劃法的原理：動態規劃法的基本思想與分治法類似，也是將待求解的問題分解爲若干個子問題，按順序求解子階段，前一個子問題的解，爲後一個子問題的求解提供了有用的信息。在求解任一個子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。依次解決各子問題，最後一個子問題就是初始問題的解。

能採用動態規劃求解的問題的一般要具有3個性質：

1、最優化原理；

2、無後效性；

3、有重疊子問題。