動態(tài)規(guī)劃（Dynamic Programming，簡稱DP）是一種常用于優(yōu)化問題的算法思想，通常用于在計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)學(xué)和數(shù)學(xué)等領(lǐng)域解決最優(yōu)化問題。它的核心思想是將大問題劃分為小問題，通過解決小問題來解決大問題。在本文中，我們將介紹動態(tài)規(guī)劃的原理、經(jīng)典案例以及示例代碼。
原理
動態(tài)規(guī)劃的核心思想是將一個(gè)問題分解成若干子問題，逐步求解子問題的最優(yōu)解，從而得到原問題的最優(yōu)解。動態(tài)規(guī)劃包括以下幾個(gè)步驟：
- 定義問題的狀態(tài)：首先需要確定問題的狀態(tài)，即描述問題的變量。狀態(tài)可以是一個(gè)數(shù)值、一個(gè)數(shù)組、一個(gè)字符串或者更復(fù)雜的結(jié)構(gòu)。
- 定義狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程是將問題的狀態(tài)轉(zhuǎn)移為下一個(gè)狀態(tài)的函數(shù)。通過狀態(tài)轉(zhuǎn)移方程，可以計(jì)算出當(dāng)前狀態(tài)下的最優(yōu)解。
- 確定初始狀態(tài)：初始狀態(tài)是問題的起點(diǎn)，它是無法通過狀態(tài)轉(zhuǎn)移方程計(jì)算出來的。因此，需要明確地給出初始狀態(tài)。
- 確定終止?fàn)顟B(tài)：終止?fàn)顟B(tài)是問題的終點(diǎn)，它是已知的，通常是問題的目標(biāo)狀態(tài)。
- 求解最優(yōu)解：通過狀態(tài)轉(zhuǎn)移方程和初始狀態(tài)，可以遞推計(jì)算出所有狀態(tài)的最優(yōu)解。最終，可以得到問題的最優(yōu)解。
經(jīng)典案例
1. Fibonacci數(shù)列
Fibonacci數(shù)列是一種經(jīng)典的動態(tài)規(guī)劃問題。其定義如下：
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) （n>=2）
這個(gè)問題可以使用DP來解決。首先定義一個(gè)狀態(tài)數(shù)組f，其中f[i]表示第i個(gè)Fibonacci數(shù)的值。由于f[0]和f[1]已知，所以可以先將它們填充到數(shù)組中。然后，從f[2]開始，根據(jù)狀態(tài)轉(zhuǎn)移方程計(jì)算出每個(gè)Fibonacci數(shù)的值，最后返回f[n]即可。
C++代碼示例：
int fibonacci(int n) {
if (n <= 1) {
return n;
}
int f[n+1];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
2.最長公共子序列
最長公共子序列（Longest Common Subsequence，簡稱LCS）是另一個(gè)經(jīng)典的動態(tài)規(guī)劃問題。給定兩個(gè)字符串X和Y，求它們的最長公共子序列。其中，子序列指的是從原序列中刪除一些元素后得到的序列，不一定要相鄰。
例如，對于字符串"ABCDGH"和" AEDFHR"，最長公共子序列為"ADH"，長度為3。
我們需要創(chuàng)建一個(gè)二維數(shù)組dp，其中dp[i][j]表示序列1的前i個(gè)字符和序列2的前j個(gè)字符之間的LCS的長度。然后，我們可以根據(jù)下面的遞歸式填充dp數(shù)組：
if (sequence1[i-1] == sequence2[j-1])
dp[i][j] = dp[i-1][j-1] + 1
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
最終結(jié)果將存儲在dp[m][n]中，其中m是序列1的長度，n是序列2的長度。示例代碼如下：
int lcs(string s1, string s2) {
int m = s1.length();
int n = s2.length();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
這段代碼中，我們首先定義了兩個(gè)字符串s1和s2，然后創(chuàng)建了一個(gè)二維向量dp。接下來，我們使用嵌套的for循環(huán)來填充dp數(shù)組，最后返回dp[m][n]作為最長公共子序列的長度。
3.背包問題
背包問題，是指有一個(gè)固定大小的背包，需要選擇一些物品放入其中，每個(gè)物品有自己的重量和價(jià)值，要求選擇的物品重量不超過背包容量，使得放入背包的物品總價(jià)值最大。
0/1背包問題：每個(gè)物品只能選擇 0 或 1 個(gè)
定義狀態(tài) 表示前
個(gè)物品中，選擇若干個(gè)放入重量不超過
的背包中所能獲得的最大價(jià)值。
需要考慮兩種情況：
不選物品 ，此時(shí)
；
選物品 ，此時(shí)
。
最終，所求解即為 。
代碼實(shí)現(xiàn)：
// w: 物品重量數(shù)組
// v: 物品價(jià)值數(shù)組
// c: 背包容量
int Knapsack01(vector<int>& w, vector<int>& v, int c)
{
int n = w.size();
// dp[i][j]表示將前i個(gè)物品放入容量為j的背包中所能獲得的最大價(jià)值
vector<vector<int>> dp(n+1, vector<int>(c+1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= c; j++) {
if (j < w[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1]);
}
}
}
return dp[n][c];
}
int main()
{
vector<int> w = {2, 3, 4, 5};
vector<int> v = {3, 4, 5, 6};
int c = 8;
cout << "0/1 Knapsack Problem: " << Knapsack01(w, v, c) << endl;
return 0;
}
完全背包問題：每個(gè)物品可以選擇任意個(gè)
需要考慮兩種情況：
不選物品 ，此時(shí)
；
選物品 ，此時(shí)
。
最終，所求解即為 。
// w: 物品重量數(shù)組
// v: 物品價(jià)值數(shù)組
// c: 背包容量
int KnapsackUnbounded(vector<int>& w, vector<int>& v, int c)
{
int n = w.size();
// dp[i][j]表示將前i個(gè)物品放入容量為j的背包中所能獲得的最大價(jià)值
vector<vector<int>> dp(n+1, vector<int>(c+1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= c; j++) {
if (j < w[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-1]]+v[i-1]);
}
}
}
return dp[n][c];
}
int main()
{
vector<int> w = {2, 3, 4, 5};
vector<int> v = {3, 4, 5, 6};
int c = 8;
cout << "Unbounded Knapsack Problem: " << KnapsackUnbounded(w, v, c) ;
return 0;
}
總結(jié)一下，動態(tài)規(guī)劃是解決許多優(yōu)化問題的有用工具。通過將大問題分解為子問題，我們可以使用動態(tài)規(guī)劃來找到最優(yōu)解。在實(shí)踐中，動態(tài)規(guī)劃通常用于優(yōu)化問題的解決方案，以便在較短的時(shí)間內(nèi)找到最優(yōu)解。在使用動態(tài)規(guī)劃時(shí)，我們需要確定狀態(tài)轉(zhuǎn)移方程，并設(shè)計(jì)適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)來存儲計(jì)算過程中產(chǎn)生的中間結(jié)果。
