动态规划

什么是动态规划

动态规划（Dynamic Programming, DP）是一种用来解决一类最优化问题的算法思想。简单来说，动态规划将一个复杂的问题分解成若干个问题，通过综合子问题的最优解来得到原问题的最优解。需要注意的是，动态规划会将每个求解的子问题的解记下来，这样当下次碰到同样的子问题时，就可以直接使用之前记录的结果，而不是重复计算。注意：虽然动态规划采用这种方式来提高计算效率，但不能说这种做法就是动态规划的核心。

动态规划前提

一个问题必须拥有重叠子问题和最优子结构才能使用动态规划。

重叠子问题

如果一个问题可以被分解为若干个子问题，且这些子问题会重复出现，那么就称这个问题拥有重叠子问题(Overlapping Subproblems)。动态规划通过记录重叠子问题的解，来使得下次碰到相同的子问题时直接使用之前记录的结果，以此避免大量重复计算。因此，一个问题必须拥有重叠子问题，才能使用动态规划去解决。

最优子结构

如果一个问题的最优解可以由其子问题的最优解有效的构造出来，那么称这个问题拥有最优子结构(Optimal Sbustructure)。最优子结构保证了动态规划中原问题的最优解可以由子问题的最优解推导出来。因此，一个问题必须拥有最优子结构，才能使用动态规划去解决。例如树塔问题中，每一个位置的dp值都可以由它的两个子问题推导出来。

例如：树塔问题的最优子结构为dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + f[i][j]

树塔问题

树塔问题示意图

问题描述： 如图所示，将一些数字排列成树塔的形状，其中第一层有一个数字，第二层有两个数字……第n层有n个数字。现在要从第一层走到第n层，每次只能走向下一层连接的两个数字中的一个，问：最后将路径上所有数字相加得到的和最大时多少？

思路： 贪心的话，从上往下，每一次都选最大的，只能保证当前是最大的，即子问题满足，但是最后却不满足，当前最大的路线不一定最后是最大的。穷尽的时间复杂度为 $O(2^{n})$ ，穷尽之所以复杂度大是因为重复的太多了，比如你按5->8->7的路线走，然后再按5->3->7的路线走，还要再走一遍关于7的路线，所以如果能记录当前的最大值就可以省去很多时间和空间。

具体实现：

dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + f[i][j]

f[i][j]存放第i层的第j个数字,那么就有f[1][1]=5,f[2][1]=8 ...

dp[i][j]称为问题的状态，上面的式子称为状态转移方程 ,它把状态dp[i][j]转移为dp[i+1][j]和dp[i+1][j+1]。可以发现，状态dp[i][j]只与第i+1层的状态有关，而与其他层的状态无关，这样层号为i的状态就总是可以由层号为i+1的两个子状态得到。那么，如果总是将层号增大，什么时候会到头呢？可以发现，树塔的最后一层的dp值总是等于元素本身，即dp[n][j] == f[n][j]，把这种可以直接确定其结构的部分称为边界 ，而动态规划的递推写法总是从这些边界出发，通过状态转移方程扩散到整个dp数组。

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 <algorithm>
#include <array>

using namespace std;
const int maxn = 20;

int main()
{
	array<array<int,maxn>,maxn> nums;
	array<array<int,maxn>,maxn> dp;
	// 输入塔的层数
	int n=0;
	scanf("%d",&n);
	// 输入数据
	for(int i=0;i<n;++i) {
		for(int j=0;j<=i;++j) {
			scanf("%d",&(nums[i][j]));
		}
	}
	// 边界
	for(int i=0;i<n;++i) {
		dp[n-1][i] = nums[n-1][i];
	}
	// 从第n-1层不断往上计算出dp[i][j]
	for(int i=n-2;i>=0;--i) {
		for(int j=0;j<=i;++j) {
			dp[i][j] = max(dp[i+1][j],dp[i+1][j+1])+nums[i][j];
		}
	}
	printf("%d\n",dp[0][0]);
	return 0;
}

最大连续子序列

问题描述： 给定一个数字数列 $A_1,A_2,…,A_n$, 求 $i,j(1 \le i \le j \le n)$ ，使得 $A_i+…+A_j$ 最大，输出这个最大和。

样例：
-2 11 -4 13 -5 -2
显然11+(-4)+13=20为最大的选择情况，因此最大和为20

解法：

  1. 令状态dp[i]表示以A[i]作为末尾的连续序列的最大和（这里说A[i]必须作为连续序的末尾）

  2. 边界：$dp[0] = A[0]$

  3. 状态转移方程： $dp[i]= max{A[i],dp[i-1]+A[i]}$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	scanf("%d",&n);
	vector<int> A(n);
	vector<int> dp(n);
	for(int i=0;i<n;++i) {
		scanf("%d",&(A[i]));
	}
	dp[0] = A[0];
	for(int i=1;i<n;++i) {
		dp[i] = max(A[i],dp[i-1]+A[i]);
	}
	vector<int>::iterator it = max_element(dp.begin(),dp.end());
	printf("%d",*it);
}