動態規劃的引入 動態規劃(Dynamic Programming,DP)是運籌學的一個分支,是求解決策過程最優化的過程。20世紀50年代初,美國數學家貝爾曼(R.Bellman)等人在研究多階段決策過程的優化問題時,提出了著名的最優化原理,從而創立了動態規劃。動態規劃的應用極其廣泛,包括工程技術、經 ...
動態規劃的引入
動態規劃(Dynamic Programming,DP)是運籌學的一個分支,是求解決策過程最優化的過程。20世紀50年代初,美國數學家貝爾曼(R.Bellman)等人在研究多階段決策過程的優化問題時,提出了著名的最優化原理,從而創立了動態規劃。動態規劃的應用極其廣泛,包括工程技術、經濟、工業生產、軍事以及自動化控制等領域,併在背包問題、生產經營問題、資金管理問題、資源分配問題、最短路徑問題和複雜系統可靠性問題等中取得了顯著的效果。
——百度百科
動態規劃與分治法相似,都是通過組合子問題來求解原問題。根據演算法導論,Programming 譯作“表格法”而不是“編寫程式”,“動態規劃”這個名字網路上有段子說是用來討要經費的。
包含如下特征:
- 階段 問題被劃分為若幹階段,每階段受先前階段影響
- 狀態 描述該階段特定子問題的若幹變數
- 決策 從一個狀態演變到下一階段某個狀態的選擇
- 最優子結構 一個最優化策略的子策略總是最優的
- 無後效性 已經求解的子問題,不會再受到後續決策的影響
OI 中 DP 的含義被極大地擴展了,下麵提取兩大核心特征
-
狀態 一個含義清晰且獨立 (即無後效性) 的子問題 $I $
▶ 使用 \(f_I\) 表示子問題 $ I$ 的答案
▶ 可能需要引入輔助子問題 $g_J, h_K, · · · $
-
轉移 答案 \(f_I\) 通過狀態轉移方程由其它子問題共同計算得到
▶ 以狀態為點,轉移為邊,構成有向無環圖 (DAG)
▶ 邊界條件與平凡子問題
▶ 解空間中的任意元素都被恰當考慮
如何理解最後一句話?按照問題類型分類
- 最優化 (k-優) 最優解能被考慮到,這依賴於最優子結構
- 計數 (概率, 期望) 計數對象 (事件) 能被不重不漏地處理
使用動態規劃需要滿足以下性質:
1.最優子結構性質。動態規划下一階段的最優解應該能由前面已經算出的各階段的最優解導出。
舉個簡單的例子。下麵是一個地圖,我們要找一條從左下角(起點)到右上角(終點)、只向右和向上走的路徑。
如果要讓路徑經過的數字總和最大,那麼最優路徑是下麵這條:
可以驗證,對於最優路徑上的任意一點,最優路徑從起點到該點的部分,也正是從起點到該點的所有路徑中數字總和最大的那一條。這就叫「滿足最優子結構」。
現在換一個「最優」的標準,要求路徑經過的數字總和的絕對值最小。那麼最優路徑是下麵這條:
但是,對於最優路徑上 -4 這個點,最優路徑從起點到該點的部分,卻不是從起點到該點的所有路徑中,數字總和的絕對值最小的那一條,因為下麵這條路徑上數字總和的絕對值更小:
這就叫「不滿足最優子結構」。
常見的最優化問題,問法一般都是「最大」「最小」,不太會出現「絕對值最小」這種奇葩的最優化標準。而問「最大」「最小」的問題,一般都是滿足最優子結構的。 (慄子來自知乎 作者:王贇 Maigo)
2.無後效性。動態規劃要求已經求解出的子問題不能受後續階段的影響,也就是說,動態規劃時對於狀態空間的遍歷應該構成一個有向無環圖。
例如CSP-J 2020 方格取數 本題可以向上向下走,如果直接設計 \(f(i, j)\) 的狀態表示走到格子 \((i, j)\),那麼如下圖,狀態轉移形成環形,會產生後效性。

此時進行動態規劃時就要設計一個無後效性的狀態,如在原狀態 \(f(i, j)\) 的基礎上加一維表示方向。
3.子問題重疊。動態規劃之所以優於爆搜,就是因為它以空間換時間的形式記錄了前面所有狀態的最優解。
狀態、階段和決策則是動態規劃的三要素。動態規劃將相同的計算作用在各階段的同類子問題,這種計算被稱為狀態轉移方程,其實也就是決策,將當前狀態轉移到下一狀態或更新下一狀態,或是根據前面的狀態計算當前狀態。
一般都是通過數字三角形引入:
Number Triangles
題目描述
觀察下麵的數字金字塔。
寫一個程式來查找從最高點到底部任意處結束的路徑,使路徑經過數字的和最大。每一步可以走到左下方的點也可以到達右下方的點。
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
在上面的樣例中,從 \(7 \to 3 \to 8 \to 7 \to 5\) 的路徑產生了最大
輸入格式
第一個行一個正整數 \(r\) ,表示行的數目。
後面每行為這個數字金字塔特定行包含的整數。
輸出格式
單獨的一行,包含那個可能得到的最大的和。
樣例 #1
樣例輸入 #1
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
樣例輸出 #1
30
【數據範圍】 對於 \(100\%\) 的數據,\(1\le r \le 1000\),所有輸入在 \([0,100]\) 範圍內。
方法一:遞歸
int solve(int i, int j) {
return a[i][j] + (i == n ? 0 : max(solve(i + 1, j), solve(i + 1, j + 1)));
}
如果數據範圍很小,可以考慮爆搜,所有路徑條數為 \(2^{n - 1}\) ,所以時間複雜度為 \(\Theta(2^n)\) ,無法接受。
方法二:遞推
時間複雜度 \(\Theta(n^2)\)
#include<bits/stdc++.h>
using namespace std;
int a[1001][1001];
int main() {
int n = 0;
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j <= i; j++)
cin >> f[i][j];
for (int i = n - 2; i >= 0; i--)
for (int j = 0; j <= i; j++)
f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
cout << f[0][0];
}
方法三:記憶化搜索
我們畫出來方法一的搜索樹:
用紅色圈起來的地方顯然是重覆計算了,可以用一個數組來記錄搜過的狀態,如果再次搜到已搜過的狀態,就直接返回記錄的值,這樣沒有了重覆搜索,時間複雜度是 \(\Theta(n^2)\).
memset(f, -1, sizeof(f));
int solve(int i, int j) {
if (f[i][j] >= 0) return f[i][j];
return f[i][j] = a[i][j] + (i == n ? 0 :
max(solve(i + 1, j), solve(i + 1, j + 1)));
}