動態(tài)規(guī)劃是什么
動態(tài)規(guī)劃（Dynamic Programming敏簿，DP）是運(yùn)籌學(xué)的一個分支节沦，是求解決策過程最優(yōu)化的過程。20世紀(jì)50年代初柔纵，美國數(shù)學(xué)家貝爾曼（R.Bellman）等人在研究多階段決策過程的優(yōu)化問題時漏益，提出了著名的最優(yōu)化原理墩邀，從而創(chuàng)立了動態(tài)規(guī)劃。
我們把要解決的一個大問題轉(zhuǎn)換成若干個規(guī)模較小的同類型問題宫盔，當(dāng)我們求解出這些小問題的答案融虽，大問題便不攻自破。這就是動態(tài)規(guī)劃灼芭。
看一個很經(jīng)典的介紹 DP 的問題：
“How should i explain Dynamic Programming to a 4-year-old?“
writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper
"What's that equal to?"
counting "Eight!"
writes down another "1+" on the left
"What about that?"
quickly "Nine!"
"How'd you know it was nine so fast?"
"You just added one more"
"So you didn't need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say 'remembering stuff to save time later'"
這個估計大家都能看懂有额，就不解釋了。動態(tài)規(guī)劃其實就是把要解決的一個大問題轉(zhuǎn)換成若干個規(guī)模較小的同類型問題。那這里的關(guān)鍵在于小問題的答案谆吴，可以進(jìn)行重復(fù)使用倒源，比如經(jīng)典的爬樓梯問題。
這種思想的本質(zhì)是：一個規(guī)模較大的問題（可以用兩三個參數(shù)表示）句狼，通過若干規(guī)模較小的問題的結(jié)果來得到的（通常會尋求到一些特殊的計算邏輯笋熬，如求最值等）
我們一般看到的狀態(tài)轉(zhuǎn)移方程，基本類似下面的公式（注：i腻菇、j胳螟、k 都是在定義DP方程中用到的參數(shù)。opt 指代特殊的計算邏輯筹吐，大多數(shù)情況下為 max 或 min糖耸。func 指代邏輯函數(shù)）：
- dp[i] = opt(dp[i-1])+1
- dp[i][j] = func(i,j,k) + opt(dp[i-1][k])
- dp[i][j] = opt(dp[i-1][j-1],dp[i-1][j])+arr[i][j]
- dp[i][j] = opt(dp[i-1][j] + xi, dp[i][j-1] + yj, ...)
- ...
基本思路
動態(tài)規(guī)劃是一個求最值的過程，既然是要求最值丘薛，核心問題是什么呢嘉竟？求解動態(tài)規(guī)劃的核心問題是窮舉。因為要求最值洋侨，肯定要把所有可行的答案窮舉出來舍扰，然后在其中找最值。
首先希坚，動態(tài)規(guī)劃的窮舉有點特別边苹，因為這類問題存在“重疊子問題”，如果暴力窮舉的話效率會極其低下裁僧，所以需要“備忘錄”或者“DP table”來優(yōu)化窮舉過程个束，避免不必要的計算。
而且聊疲，動態(tài)規(guī)劃問題一定會具備“最優(yōu)子結(jié)構(gòu)”茬底，才能通過子問題的最值得到原問題的最值。
最后售睹，雖然動態(tài)規(guī)劃的核心思想就是窮舉求最值桩警，但是問題可以千變?nèi)f化，窮舉所有可行解其實并不是一件容易的事昌妹，只有列出正確的“狀態(tài)轉(zhuǎn)移方程”才能正確地窮舉。
整體框架
- 狀態(tài)轉(zhuǎn)移方程
- 備忘錄存儲重復(fù)子問題
- 最小子問題
- 求最值
斐波那契數(shù)列
斐波那契數(shù)列不算動態(tài)規(guī)劃握截，但是解決問題的思路與動態(tài)規(guī)劃很像飞崖，再加上大家上學(xué)的時候基本都接觸過斐波那契數(shù)列，通過它來理解動態(tài)規(guī)劃就很不錯了谨胞。
斐波那契數(shù)列的數(shù)學(xué)形式就是遞歸的固歪，寫成代碼就是這樣：
int fib(int N) {
if (N == 1 || N == 2) return 1;
return fib(N - 1) + fib(N - 2);
}
這個遞歸，相信有不少人能看出問題，子問題被不斷計算牢裳，以N=20為例
fib(20) = fib(19) + fib(18) = fib(18) + fib(17) + fib(18)
寫到這里逢防，已經(jīng)發(fā)現(xiàn)，fib(18)已經(jīng)被計算多次蒲讯，效率很低下忘朝。
所以引入帶備忘錄的遞歸算法，把每次計算的子結(jié)果的值進(jìn)行存儲判帮，后面就不需要重復(fù)計算了局嘁。整改之后的代碼
int fib(int N) {
int[] dp = int int[N];
// 最小子問題
dp[1] = dp[2] = 1;
for (int i = 3; i <= N; i++) {
// 狀態(tài)轉(zhuǎn)移方程
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
例子：最長回文串
問題：給定一個字符串 s，找到 s 中最長的回文子串晦墙。你可以假設(shè) s 的最大長度為 1000悦昵。
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
思路：對于一個子串而言晌畅，如果它是回文串但指，并且長度大于2，那么將它首尾的兩個字母去除之后抗楔，它仍然是個回文串枚赡。例如對于字符串“ababa”，如果我們已經(jīng)知道“bab” 是回文串谓谦，那么“ababa” 一定是回文串贫橙，這是因為它的首尾兩個字母都是“a”。
于是得到我們的狀態(tài)轉(zhuǎn)移方程：
dp[i][j] 表示i到j(luò)之間的字符串是否是回文串
dp[i][j] = dp[i+1][j-1] and (s[i] eq s[j])
最小子問題：當(dāng)s[i] eq s[j]反粥，子串長度是2或3卢肃，不需要檢查子串是否回文串，即j-i<=2
public String longestPalindrome(String s) {
if (s == null || s.length() <= 1) {
return s;
}
int len = s.length();
int maxLen = 1;
int left = 0;
int right = 0;
boolean[][] dp = new boolean[len][len];
char[] chars = s.toCharArray();
// 如果i從0開始才顿，那么對應(yīng)abba這樣的字符串莫湘，bb這個子串在遍歷過程中沒法被當(dāng)做子問題進(jìn)行存儲
for (int i=len-2; i>=0; i--) {
for (int j=i+1; j<len; j++) {
if (chars[i] == chars[j]) {
if (j-i <= 2) { // 最小字問題
if (j-i+1 > maxLen) {
maxLen = j-i+1;
left = i;
right = j;
}
dp[i][j] = true;
}else if (dp[i+1][j-1]) { // 子問題
if (j-i+1 > maxLen) {
maxLen = j-i+1;
left = i;
right = j;
}
dp[i][j] = true;
}
}
}
}
return s.substring(left, right + 1);
}
