第3章　動態(tài)規(guī)劃進階算法

動態(tài)規(guī)劃（Dynamic Programming，DP）是運籌學(xué)的一個分支，是求解決策過程最優(yōu)化的數(shù)學(xué)方法，其核心思想在于把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個求解。

動態(tài)規(guī)劃程序設(shè)計是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不像搜索或數(shù)值計算那樣，具有一個標準的數(shù)學(xué)表達式和明確清晰的解題方法。動態(tài)規(guī)劃程序設(shè)計往往針對一種最優(yōu)化問題，由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而對于不同的問題，動態(tài)規(guī)劃的設(shè)計方法有各具特色的解題方法，而不存在一種萬能的動態(tài)規(guī)劃算法可以解決各類最優(yōu)化問題。讀者在學(xué)習(xí)時，除了要正確理解基本概念和方法，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。讀者可以通過對若干有代表性的問題的動態(tài)規(guī)劃算法進行分析、討論，逐漸學(xué)會并掌握這一設(shè)計方法。本章將介紹一些動態(tài)規(guī)劃進階算法，以及一些動態(tài)規(guī)劃的優(yōu)化方法。