算法簡(jiǎn)述
動(dòng)態(tài)規(guī)劃(dynamic programming, 簡(jiǎn)稱(chēng)dp)是一種應(yīng)用十分廣泛的算法。它可以理解成是對(duì)枚舉法的一種優(yōu)化椎麦。通常在求解一個(gè)復(fù)雜的最優(yōu)解問(wèn)題時(shí)，我們會(huì)把它拆分成很多子問(wèn)題乐严，然后各個(gè)擊破杏慰，最后匯總起來(lái)得到最終答案。如果我們采用枚舉法列舉所有情況誉结，你會(huì)發(fā)現(xiàn)會(huì)有很多重復(fù)的子問(wèn)題鹅士。而dp的核心思想就是：將很多子問(wèn)題的結(jié)果儲(chǔ)存起來(lái)，以空間換取時(shí)間的方式惩坑，盡可能地避免重復(fù)的計(jì)算量掉盅。
有人做過(guò)一個(gè)這樣的比喻：你追一個(gè)MM的時(shí)候，需要對(duì)該MM身邊的各閨中密友都好以舒，這樣你追MM這個(gè)問(wèn)題就分解為對(duì)其MM朋友的問(wèn)題趾痘，只有把這些問(wèn)題都解決了，最終你才能追到MM蔓钟。
動(dòng)態(tài)規(guī)劃的兩個(gè)最重要的要素就是：
- 狀態(tài)的定義
- 狀態(tài)的轉(zhuǎn)移
題目鏈接
hdu-2084 數(shù)塔
題意：
給定類(lèi)似下圖的一個(gè)數(shù)塔永票，要求從頂層走到底層，若每一步只能走到相鄰的結(jié)點(diǎn)，則經(jīng)過(guò)的結(jié)點(diǎn)的數(shù)字之和最大是多少侣集？
解法：
首先键俱，從上到下的模型我們可以倒過(guò)來(lái)。這樣世分，問(wèn)題就變成了：求從底層走到頂層的數(shù)字之和的最大值了编振。記第i層第j個(gè)點(diǎn)的數(shù)值為a[i][j]
- 狀態(tài)定義：
dp[i][j]表示從底層走到(i, j)點(diǎn)所能達(dá)到最大的數(shù)字之和； - 狀態(tài)轉(zhuǎn)移：
第i層第j個(gè)點(diǎn)可由第i+1層j或j+1的點(diǎn)走過(guò)來(lái)臭埋，所以dp[i][j]=max(dp[i+1][j], dp[i+1][j+1]) + a[i][j] for i in range(n-1) - 初始條件：
dp[n-1][j]=a[n-1][j] for j in range(n)
核心代碼：
System.arraycopy(a[n - 1], 0, dp[n - 1], 0, n);
for (int i = n - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j];
}
}
