C++动态规划算法简析

动态规划

动态规划主要用于求全局最优解，通常可以解决以下问题：

1. 优化问题：例如最短路径问题、背包问题、调度问题等，这些问题通常具有子问题重叠的特点，因此可以通过动态规划的方式避免重复计算，从而提高算法的效率。
2. 求最大值或最小值问题：例如最长上升子序列、最大连续子数组和等，这些问题通常可以通过建立一个状态转移方程来逐步求解最终结果。
3. 求方案数问题：例如路径计数问题、背包问题、组合问题等，这些问题通常可以通过建立一个状态转移方程来逐步求解方案数。
4. 求最优方案问题：例如字符串编辑距离、图像识别、语音识别等，这些问题通常可以通过建立一个状态转移方程来逐步求解最优方案。

解题思路

动态规划运用分治的思想，将大问题拆解成许多小问题。
比如01背包问题，首先求只装入一个物品时的最大价值，再此基础再求装入两个物品，最终求得计入所有物品时的最大价值。
再比如Floyd算法，首先求解只能经过一个结点的情况，再此基础上，再计算经过两个节点的情况，以此类推，最终找到多源最短路解。

解题步骤如下：

1. 定义变量和状态
2. 找到约束条件
3. 确认求值属性（基于问题求最大值、最小值或者其他）
4. 列出状态转移方程

具体例子

01背包问题

给定一个重量数组v和价值数组w，以及一个背包的最大承重量m，每个物品只能用一次，求在不超过背包最大承重量的前提下，能够装入背包的物品的最大总价值。v=[1,2,3,4] w=[3,2,4,5]。

1. 首先确定变量。i: 当前最多装入物品数（比如1当前背包只能装一个物品）,j :当前背包已使用容量（比如4代表背包现在已经用了4个体积）
2. 找到约束条件。每个物品只能用一次、不超过背包最大承重量
3. 确认求值属性。求装入背包的最大总价值
4. 列出状态转移方程。f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i])

for(int i = 1; i <= n; ++i) // 选取多少个物品
	for(int j = 0; j <= m; j++){ // 容积
		f[i][j] = f[i-1][j];
		if(j > v[i]) // 如果总容积大于当前物品重量
			f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]); // 找到在没选择该物品前的最大价值
	}
1
2
3
4
5
6
7