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