動态規劃（Dynamic Programming，DP）是運籌學的一個分支，是求解決策過程最優化的過程。整體架構：狀态轉移方程、備忘錄存儲重複子問題、最小子問題、求最值。斐波那契數列不算動态規劃，但是解決問題的思路與動态規劃很像，再加上大家上學的時候基本都接觸過斐波那契數列，通過它來了解動态規劃就很不錯了。
動态規劃是什麼
動态規劃（Dynamic Programming，DP）是運籌學的一個分支，是求解決策過程最優化的過程。20世紀50年代初，美國數學家貝爾曼（R.Bellman）等人在研究多階段決策過程的優化問題時，提出了著名的最優化原理，進而創立了動态規劃。
我們把要解決的一個大問題轉換成若幹個規模較小的同類型問題，當我們求解出這些小問題的答案，大問題便不攻自破。這就是動态規劃。
看一個很經典的介紹 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'"
這個估計大家都能看懂，就不解釋了。動态規劃其實就是把要解決的一個大問題轉換成若幹個規模較小的同類型問題。那這裡的關鍵在于小問題的答案，可以進行重複使用，比如經典的爬樓梯問題。
這種思想的本質是：一個規模較大的問題（可以用兩三個參數表示），通過若幹規模較小的問題的結果來得到的（通常會尋求到一些特殊的計算邏輯，如求最值等）
我們一般看到的狀态轉移方程，基本類似下面的公式（注：i、j、k 都是在定義DP方程中用到的參數。opt 指代特殊的計算邏輯，大多數情況下為 max 或 min。func 指代邏輯函數）：
- 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, ...)
- ...
基本思路
動态規劃是一個求最值的過程，既然是要求最值，核心問題是什麼呢？求解動态規劃的核心問題是窮舉。因為要求最值，肯定要把所有可行的答案窮舉出來，然後在其中找最值。
首先，動态規劃的窮舉有點特别，因為這類問題存在“重疊子問題”，如果暴力窮舉的話效率會極其低下，是以需要“備忘錄”或者“DP table”來優化窮舉過程，避免不必要的計算。
而且，動态規劃問題一定會具備“最優子結構”，才能通過子問題的最值得到原問題的最值。
最後，雖然動态規劃的核心思想就是窮舉求最值，但是問題可以千變萬化，窮舉所有可行解其實并不是一件容易的事，隻有列出正确的“狀态轉移方程”才能正确地窮舉。
整體架構
- 狀态轉移方程
- 備忘錄存儲重複子問題
- 最小子問題
- 求最值
斐波那契數列
斐波那契數列不算動态規劃，但是解決問題的思路與動态規劃很像，再加上大家上學的時候基本都接觸過斐波那契數列，通過它來了解動态規劃就很不錯了。
斐波那契數列的數學形式就是遞歸的，寫成代碼就是這樣：
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)
寫到這裡，已經發現，fib(18)已經被計算多次，效率很低下。
是以引入帶備忘錄的遞歸算法，把每次計算的子結果的值進行存儲，後面就不需要重複計算了。整改之後的代碼
int fib(int N) {
int[] dp = int int[N];
// 最小子問題
dp[1] = dp[2] = 1;
for (int i = 3; i <= N; i++) {
// 狀态轉移方程
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
例子：最長回文串
問題：給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
思路：對于一個子串而言，如果它是回文串，并且長度大于2，那麼将它首尾的兩個字母去除之後，它仍然是個回文串。例如對于字元串“ababa”，如果我們已經知道“bab” 是回文串，那麼“ababa” 一定是回文串，這是因為它的首尾兩個字母都是“a”。
于是得到我們的狀态轉移方程：
dp[i][j] 表示i到j之間的字元串是否是回文串
dp[i][j] = dp[i+1][j-1] and (s[i] eq s[j])
最小子問題：當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開始，那麼對應abba這樣的字元串，bb這個子串在周遊過程中沒法被當做子問題進行存儲
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);
}
__EOF__
歡迎轉載，但請注明出處！
歡迎大家一起交流學習！如果有什麼疑問，大家可以在評論區一起交流！
如果您覺得文章對您有幫助，可以點選文章右下角【推薦】一下。您的鼓勵是我的最大動力！