动态规划的核心为状态表示和状态计算:

  • 状态表示
    • 集合
    • 属性
  • 状态计算：递归式

背包问题

给定一组物品，每个物品都有重量和价值两个属性，同时给定一个容量有限的背包。要求选择一些物品放入背包中，使得放入背包的物品总价值最大，同时背包中物品的总重量不能超过背包的容量。

通用递归式：
$$
f[i][j] = max(f[i-1][j - k * w[i]] + v[i] * k) \quad k = 0, 1, \cdots, s[i]
$$
其中i表示前i个物品，j表示已占用的容量，s[i]表示每个物品的数量上限，w[i]和v[i]分别表示物品的重量和价值

01背包问题

01背包问题要求每个物品只能选择放入或不放入背包，即不能选择物品的一部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 1e3+5;
int n, m;
int v[N], w[N];
int dp[N];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= w[i]; j--) {
			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
		}
	}
	cout << dp[m] << endl;

	return 0;
}

完全背包问题

完全背包问题规定每种物品都有无限件可用，即可以选择放入背包中任意数量的同一种物品。
$$
f[i][j] = max(f[i-1][j], f[i-1][j - w] + v, \cdots, f[i-1][j - k*w] + k * v) \
$$
同时有
$$
f[i][j-w] = max(f[i-1][j-w], f[i-1][j - 2 * w] + v, \cdots, f[i-1][j - k * w] + (k-1) * v)
$$
因此有
$$
f[i][j] = max(f[i-1][j], f[i][j-w] + v)
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 1e3+5;
int n, m;
int v[N], w[N];
int dp[N];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

	for (int i = 1; i <= n; i++) {
		for (int j = v[i]; j <= m; j++) 
		{
			dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
		}
	cout << dp[m] << endl;

	return 0;
}

多重背包问题

多重背包问题规定每种物品有有限个，即对每种物品有一个数量限制s[i]

二进制优化：将s[i]分解成$2^0, 2^1, 2^2, \cdots, 2^k, c$，其中$2^{k+1} - 1 + c = s[i]$，这样就能将多重背包问题转化为01背包问题，复杂度为$O(nmlogs)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int N = 1e5+5;
int n, m;
int v[N], w[N];
int dp[N];

int main() {
	cin >> n >> m;

	int idx = 0;
	for (int i = 1; i <= n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		int k = 1;
		while (k <= c) {
			v[++idx] = a * k
			w[idx] = b * k;
			c -= k;
			k <<= 1;
		}
		if (c > 0) {
			v[++idx] = a * c;
			w[idx] = b * c;
		} 
	}
	n = idx;
	for (int i = 1; i <= n; i++)
		for (int j = m; j >= v[i]; j--)
			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
	cout << dp[n] << endl;
	return 0;
}

分组背包问题

分组背包问题规定有n个物品和一个容量为m的背包，这些物品被划分为k个组。每个组内有若干个物品，同一组内的物品相互冲突，最多只能选择一个放入背包中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int N = 1e5 + 5;
int n, m;
int v[N][N], w[N][N], s[N];
int dp[N];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		for (int j = 0; j < s[i]; j++) 
			cin >> v[i][j] >> w[i][j];
		
	}

	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= 0; j--) {
			for (int k = 0; k < s[i]; k++)
				if (v[i][k] <= j)
					dp[j] = max(dp[j], dp[j-w[i][k]] + v[i][k]);
		}
	}
	cout << dp[n] << endl;
	return 0;
}

以下是为你提供的关于上述标题的问题描述、状态转移式以及 C++代码示例：

线性DP

数字三角形

从三角形的顶部开始，每次只能向下移动到相邻的两个数字中的一个，求从顶部到底部的路径中数字之和的最大值。

1
2
3
4
   2
  3 4
 6 5 7
4 1 8 3

状态转移式：
设 $dp[i][j]$ 表示从三角形顶部走到第 $i$ 行第 $j$ 列的最大数字和。对于第 $i$ 行第 $j$ 列的元素，它可以从第 $i - 1$ 行第 $j - 1$ 列或第 $i - 1$ 行第 $j$ 列转移过来（需考虑边界情况），状态转移方程为：
$$
dp[i][j]=\begin{cases}
triangle[i][j]+dp[i - 1][j], & j = 0\
triangle[i][j]+\max(dp[i - 1][j - 1],dp[i - 1][j]), & 0 < j < i\
triangle[i][j]+dp[i - 1][j - 1], & j = i
\end{cases}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>
using namespace std;

int triangleDP(vector<vector<int>>& triangle) {
    int n = triangle.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    dp[0][0] = triangle[0][0];
    for (int i = 1; i < n; ++i) {
        dp[i][0] = triangle[i][0] + dp[i - 1][0];
        for (int j = 1; j < i; ++j) {
            dp[i][j] = triangle[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j]);
        }
        dp[i][i] = triangle[i][i] + dp[i - 1][i - 1];
    }
    int maxSum = 0;
    for (int j = 0; j < n; ++j) {
        maxSum = max(maxSum, dp[n - 1][j]);
    }
    return maxSum;
}

int main() {
    vector<vector<int>> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
    cout << triangleDP(triangle) << endl;
    return 0;
}

最长上升子序列（LIS）

给定一个整数序列，例如 [10, 9, 2, 5, 3, 7, 101, 18]，找出其中最长的严格递增子序列的长度。

状态转移式：
设 $dp[i]$ 表示以第 $i$ 个元素结尾的最长上升子序列的长度。则 $dp[i]=\max_{j < i, nums[j] < nums[i]}(dp[j]) + 1$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
using namespace std;

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    vector<int> dp(n, 1);
    int ans = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << lengthOfLIS(nums) << endl;
    return 0;
}

还有优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
using namespace std;

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    vector<int> dp(n, 1);
    int len = 1;
    dp[0] = nums[0];
    for (int i = 1; i < n; ++i) {
	    int l = 0, r = len;
		while (l < r) {
			int mid = (r - l) / 2 + l;
			if (dp[mid] <= nums[i])
				l = mid + 1;
			else
				r = mid;
		}
		len = max(len, l + 1);
		dp[l] = nums[i];
    }
    return len;
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << lengthOfLIS(nums) << endl;
    return 0;
}

最长公共子序列（LCS）

给定两个字符串，例如 "ABCD" 和 "AEBD"，找出它们的最长公共子序列的长度。

状态转移式：
设 $dp[i][j]$ 表示第一个字符串的前 $i$ 个字符和第二个字符串的前 $j$ 个字符的最长公共子序列的长度。
$$
dp[i][j]=\begin{cases}
dp[i - 1][j - 1] + 1, & str1[i - 1] == str2[j - 1]\
\max(dp[i - 1][j], dp[i][j - 1]), & str1[i - 1]!= str2[j - 1]
\end{cases}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size();
    int n = text2.size();
    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 (text1[i - 1] == text2[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];
}

int main() {
    string str1 = "ABCD";
    string str2 = "AEBD";
    cout << longestCommonSubsequence(str1, str2) << endl;
    return 0;
}

4. 编辑距离

给定两个字符串，例如 "horse" 和 "ros"，可以对字符串进行插入、删除、替换操作，求将第一个字符串转换成第二个字符串所需的最少操作次数。

状态转移式：
设 $dp[i][j]$ 表示将第一个字符串的前 $i$ 个字符变成第二个字符串的前 $j$ 个字符所需的最少操作次数。
$$
dp[i][j]=\begin{cases}
dp[i - 1][j - 1], & str1[i - 1] == str2[j - 1]\
1+\min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]), & str1[i - 1]!= str2[j - 1]
\end{cases}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int minDistance(string word1, string word2) {
    int m = word1.size();
    int n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; ++i) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= n; ++j) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
            }
        }
    }
    return dp[m][n];
}

int main() {
    string str1 = "horse";
    string str2 = "ros";
    cout << minDistance(str1, str2) << endl;
    return 0;
}

区间DP

石子合并

有 $n$ 堆石子排成一排，每堆石子的数量为 $a[i]$，每次可以合并相邻的两堆石子，合并的代价为两堆石子的数量之和，求将所有石子合并成一堆的最小代价。

状态转移式：
设 $dp[i][j]$ 表示将第 $i$ 堆到第 $j$ 堆石子合并成一堆的最小代价。
$$
dp[i][j]=\begin{cases}
0, & i == j\
\min_{i\leq k < j}(dp[i][k]+dp[k + 1][j]+\sum_{t = i}^{j}a[t]), & i < j
\end{cases}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
#include <limits>
using namespace std;

int stoneMerge(vector<int>& stones) {
    int n = stones.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    vector<int> prefixSum(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        prefixSum[i] = prefixSum[i - 1] + stones[i - 1];
    }
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i + len - 1 < n; ++i) {
            int j = i + len - 1;
            dp[i][j] = numeric_limits<int>::max();
            for (int k = i; k < j; ++k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefixSum[j + 1] - prefixSum[i]);
            }
        }
    }
    return dp[0][n - 1];
}

int main() {
    vector<int> stones = {3, 4, 3};
    cout << stoneMerge(stones) << endl;
    return 0;
}

计数问题

介绍：
计数问题是指通过算法计算满足特定条件的组合或排列的数量。这类问题通常涉及组合数学、动态规划、回溯等方法。计数问题在计算机科学中非常常见，例如计算从起点到终点的路径数、计算满足某些约束条件的子集数等。

C++代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;

// 计算从(0,0)到(m-1,n-1)的路径数
int countPaths(int m, int n) {
    int dp[m][n];
    
    // 初始化第一行和第一列
    for (int i = 0; i < m; i++)
        dp[i][0] = 1;
    for (int j = 0; j < n; j++)
        dp[0][j] = 1;
    
    // 填充dp表
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[m-1][n-1];
}

int main() {
    int m = 3, n = 3;
    cout << "Number of paths: " << countPaths(m, n) << endl;
    return 0;
}

状态压缩DP

介绍：
状态压缩动态规划（State Compression DP）是一种优化动态规划的方法，通常用于处理状态空间较大的问题。通过将状态表示为二进制数或其他压缩形式，可以减少内存使用并提高计算效率。状态压缩DP常用于解决旅行商问题（TSP）、子集和问题等。

C++代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 旅行商问题（TSP）的状态压缩DP解法
int tsp(const vector<vector<int>>& dist) {
    int n = dist.size();
    int dp[1 << n][n];
    fill(dp[0], dp[1 << n], INT_MAX / 2);
    dp[1][0] = 0;  // 从起点0出发
    
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    
    int final_mask = (1 << n) - 1;
    int ans = INT_MAX;
    for (int u = 1; u < n; u++) {
        ans = min(ans, dp[final_mask][u] + dist[u][0]);
    }
    
    return ans;
}

int main() {
    vector<vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    cout << "Minimum cost for TSP: " << tsp(dist) << endl;
    return 0;
}

记忆化搜索

介绍：
记忆化搜索（Memoization）是一种优化递归算法的技术，通过存储已经计算过的子问题的结果，避免重复计算，从而提高效率。记忆化搜索通常用于动态规划问题，尤其是那些具有重叠子问题和最优子结构性质的问题。

C++代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// 记忆化搜索：计算斐波那契数列
unordered_map<int, int> memo;

int fibonacci(int n) {
    if (n <= 1) return n;
    if (memo.find(n) != memo.end()) return memo[n];
    
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
    return memo[n];
}

int main() {
    int n = 10;
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}