動態規劃法的原理

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

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

1、最優化原理；

2、無後效性；

3、有重疊子問題。