1碍彭、前言
動(dòng)態(tài)規(guī)劃和分治算法非常類(lèi)似，都是通過(guò)組合子問(wèn)題的解來(lái)求解原問(wèn)題。分治算法將問(wèn)題劃分為互不相交的子問(wèn)題庇忌，而動(dòng)態(tài)適應(yīng)于子問(wèn)題重疊的情況
動(dòng)態(tài)規(guī)劃常用于求解“最優(yōu)化問(wèn)題”舞箍，這類(lèi)問(wèn)題有很多個(gè)解，我們希望尋找最優(yōu)解（最大值或最小值）
通常按如下四個(gè)步驟來(lái)設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法：
- 刻畫(huà)一個(gè)最優(yōu)解的結(jié)構(gòu)特征
- 遞歸地定義最優(yōu)解的值
- 計(jì)算最優(yōu)解的值皆疹，通常采用自底向上方法
- 利用計(jì)算出的信息構(gòu)造一個(gè)最優(yōu)解
或者說(shuō)疏橄，動(dòng)態(tài)規(guī)劃有3個(gè)關(guān)鍵要素。
- 1略就、最佳子問(wèn)題（將復(fù)雜問(wèn)題轉(zhuǎn)化成簡(jiǎn)單問(wèn)題）
- 2捎迫、邊界條件（一般是當(dāng)數(shù)據(jù)量極少情況下的結(jié)果，比如n==0或n==1時(shí)的情況）
- 3表牢、狀態(tài)轉(zhuǎn)移方程（考慮 n-1 和 n這兩種規(guī)模時(shí)窄绒，結(jié)果之間的推導(dǎo)）
2、鋼條切割問(wèn)題
給定一段長(zhǎng)為n的鋼條和一個(gè)價(jià)格表崔兴，求解收益最大的鋼條切割方案
鋼條價(jià)格如上彰导，怎么切割才能有最大收益呢？通過(guò)鋼條價(jià)格敲茄，我們能手動(dòng)計(jì)算出鋼條最佳切割方案位谋。
定義長(zhǎng)為n的鋼條切割最大收益為Rn，假設(shè)在k位置將鋼條切成兩段能獲得最大收益堰燎，那么這兩段k和n-k肯定也是最大收益掏父，如果我們遍歷循環(huán)，可得到如下公式：
最大收益為爽待，不切割以及從1到n-1位置切割的收益最大值损同。
換一個(gè)角度重新考慮，如果從1到n-1位置切割鸟款，但左邊的鋼條不再切割膏燃，右邊的鋼條使用最佳方案切割。這樣得到的會(huì)不是也是最佳切割方案呢何什？
很明顯组哩，這種做法也是正常的，想象最終切割結(jié)果处渣，肯定也是符合這種模式的伶贰。這樣簡(jiǎn)單的遞歸更利于編碼。
動(dòng)態(tài)規(guī)劃的精髓在于保存子問(wèn)題的解罐栈，以提高效率黍衙。在編碼中我們新定義Rn，保存n長(zhǎng)度的最大收益荠诬，并采用自底向上方法琅翻，即先求R0位仁，R1，再求其它方椎，如果單純使用暴力遞歸的話(huà)聂抢，效率非常低。
public static int[] steel(int[] p){
int[] s = new int[p.length];
s[0] = 0;
int max = 0;
//因?yàn)殚L(zhǎng)度為0的鋼條棠众，切割最大收益為0琳疏，S[0]已知，所以i從1開(kāi)始
for (int i = 1; i < p.length; i++) {
max = 0;
for (int j = 1; j <= i; j++) {
//j也必須從1開(kāi)始闸拿，如果從0開(kāi)始空盼，i等于1時(shí)，s[i-j]就等于s[1]了胸墙，而s[1]還是未知值
if (max < (p[j] + s[i-j])) {
max = p[j] + s[i-j];
}
}
s[i] = max;
}
return s;
}
2我注、最大子數(shù)組和
給出一個(gè)數(shù)組，求最大子數(shù)組和迟隅。例如給出如下數(shù)組但骨，最大子數(shù)組和為20
-2, 11, -4, 13, -5, -2
此問(wèn)題解題思路和1不一樣。
仔細(xì)考慮智袭，如果設(shè)長(zhǎng)度為n的最大子數(shù)組和為Sn奔缠，那么Sn和Sn-1有什么關(guān)系呢？動(dòng)態(tài)規(guī)劃最重要的思想就是將大問(wèn)題分解為子問(wèn)題吼野，并由子問(wèn)題求解校哎。
直接考慮Sn和Sn-1，好像二者沒(méi)有任何關(guān)系瞳步，如果我們換個(gè)角度考慮闷哆，長(zhǎng)度為n的數(shù)組，且以n結(jié)尾的最大子數(shù)組和為Sn单起，這么定義的話(huà)抱怔，那么根據(jù)Sn的值，如果Sn大于0嘀倒，那么Sn+1等于Sn加上a[n]屈留，如果小于0，那么Sn+1等于a[n]测蘑。
公式為：
dp[i+1] = max(dp[i]+a[i+1] , a[i+1])
public static int getMaxSubArray(int[] array){
int[] b = new int[array.length];
int max = 0;
b[0] = array[0];
max = b[0];
for (int i = 1; i < array.length; i++) {
if (b[i-1] > 0) {
b[i] = b[i-1] + array[i];
}else {
b[i] = array[i];
}
if (max < b[i]) {
max = b[i];
}
}
return max;
}
3灌危、結(jié)語(yǔ)
動(dòng)態(tài)規(guī)劃還有其它經(jīng)典問(wèn)題，比如矩陣最少相乘次數(shù)碳胳，最長(zhǎng)公共子序列勇蝙，最優(yōu)二叉搜索樹(shù)等等。本文只講了兩個(gè)簡(jiǎn)單例子挨约，簡(jiǎn)述動(dòng)態(tài)規(guī)劃的原理浅蚪，可以更深入思考藕帜，二維的動(dòng)態(tài)規(guī)劃問(wèn)題解決烫罩，以加深理解惜傲。
以上代碼均已上傳至本人的github，歡迎訪(fǎng)問(wèn)
