1 動(dòng)態(tài)規(guī)劃
1.1 定義
動(dòng)態(tài)規(guī)劃的核心是狀態(tài)和狀態(tài)轉(zhuǎn)移方程。
在記憶化搜索中，可以為正在處理的表項(xiàng)聲明一個(gè)引用，簡(jiǎn)化對(duì)它的讀寫操作；
動(dòng)態(tài)規(guī)劃解決的是多階段決策問(wèn)題；
初始狀態(tài)→│決策１│→│決策２│→…→│決策ｎ│→結(jié)束狀態(tài)
和分治法最大的區(qū)別在于：適合于用動(dòng)態(tài)規(guī)劃的問(wèn)題，經(jīng)過(guò)分解以后得到的子問(wèn)題往往不是相互獨(dú)立的（即下一個(gè)子階段的求解是建立在上一個(gè)子階段的基礎(chǔ)之上，進(jìn)行進(jìn)一步的求解，而不是相互獨(dú)立的問(wèn)題）
動(dòng)態(tài)規(guī)劃問(wèn)題一般由難到易分為一維動(dòng)態(tài)規(guī)劃，二維動(dòng)態(tài)規(guī)劃，多維動(dòng)態(tài)規(guī)劃，以及多變量動(dòng)態(tài)規(guī)劃問(wèn)題。其中多維動(dòng)態(tài)規(guī)劃問(wèn)題又可以進(jìn)行降維。動(dòng)態(tài)規(guī)劃問(wèn)題求解的最重要的一步就是求解出 狀態(tài)轉(zhuǎn)移方程
