1 動(dòng)態(tài)規(guī)劃

1.1 定義

動(dòng)態(tài)規(guī)劃的核心是狀態(tài)和狀態(tài)轉(zhuǎn)移方程。

在記憶化搜索中，可以為正在處理的表項(xiàng)聲明一個(gè)引用，簡化對(duì)它的讀寫操作；

動(dòng)態(tài)規(guī)劃解決的是多階段決策問題；

初始狀態(tài)→│決策１│→│決策２│→…→│決策ｎ│→結(jié)束狀態(tài)

和分治法最大的區(qū)別在于：適合于用動(dòng)態(tài)規(guī)劃的問題，經(jīng)過分解以后得到的子問題往往不是相互獨(dú)立的（即下一個(gè)子階段的求解是建立在上一個(gè)子階段的基礎(chǔ)之上，進(jìn)行進(jìn)一步的求解，而不是相互獨(dú)立的問題）

動(dòng)態(tài)規(guī)劃問題一般由難到易分為一維動(dòng)態(tài)規(guī)劃，二維動(dòng)態(tài)規(guī)劃，多維動(dòng)態(tài)規(guī)劃，以及多變量動(dòng)態(tài)規(guī)劃問題。其中多維動(dòng)態(tài)規(guī)劃問題又可以進(jìn)行降維。動(dòng)態(tài)規(guī)劃問題求解的最重要的一步就是求解出 狀態(tài)轉(zhuǎn)移方程

1.2 特性