動(dòng)態(tài)規(guī)劃方法是處理分段過程的最優(yōu)化問題的一類及其有效的方法在實(shí)際生活中，有一類問題的活動(dòng)過程可以劃分成若干個(gè)階段，而且在任意階段后的行為依賴于該階段的狀態(tài)，于該階段之前的過程如何到達(dá)這種狀態(tài)的方式無關(guān)。這類問題的解決是多階段的決策過程。
最優(yōu)化化原理：多階段過程的最優(yōu)決策系列應(yīng)當(dāng)具有性質(zhì)：無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列。
問題的最優(yōu)子結(jié)構(gòu)性質(zhì)和自問題的重疊性質(zhì)是采用動(dòng)態(tài)規(guī)劃算法的2個(gè)基本要素：
1：最有子結(jié)構(gòu)性質(zhì)：原問題的最優(yōu)解白含了其子問題的最優(yōu)解
2：子問題重疊性質(zhì)：每次產(chǎn)生的子問題并不總是新的問題，有些子問題被反復(fù)計(jì)算多次。（與貪心算法的區(qū)別：貪心算法是不會計(jì)算子問題多次的。）
最優(yōu)化原理與0 1背包問題：歸結(jié)為數(shù)學(xué)規(guī)劃問題 ：
動(dòng)態(tài)規(guī)劃一般步驟：
分析最優(yōu)解的性質(zhì)，找出最優(yōu)子結(jié)構(gòu)的特征，如果所求解的問題的最優(yōu)性原理成立，則說明 動(dòng)態(tài)規(guī)劃方法有可能解決該問題。而解決問題的關(guān)鍵在于獲取各個(gè)階段的遞推關(guān)系，該遞推關(guān)系遞歸地定義最優(yōu)值，以自底向上的方式
cost(i,j) = min{c(i,j)+cost(i+1,l)} //牛B