动态规划入门
简单介绍
动态规划(dynamic programming)，简称DP。是运筹学的一个分支，我们不会学的太深，如果想要深究，请自行学习。 我们的目的是学习DP的思想，去解决一些问题。 需要注意的是，DP不是一个具体的算法，而是一种解决问题的方法。
动态规划的思想
动态规划是求解多阶段决策过程最优化的方法。 把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。 找到各个阶段之间的关系是难点！ 不明白？不需要去管这些定义，我们来看例子。
例题:1
1.矩阵取数问题
从矩阵的左上走到右下，每次只能向右或者向下走，问怎样走才能使得最后走过路径的和最大。
分析：
当然可以用刚刚学的BFS, DFS去暴力搜索出所有的矩阵，但是暴力完全体现不出任何优美。 如果用的思想，应该怎么做？？ 首先我们想到的一定是贪心策略，每次只能向右或者向下两种选择，那么 是不是只要每次都选择 右面和下面 的中，其元素最大的那个方向，最后的答案就是最大的呢？
用贪心的方法，答案是9. 但是显然有一个更大的答案 10 ，这个答案是如何得出的？ 如果你崇尚暴力的美学，当然也可以把所有的路径搜出来求一个最大值，但是请自行算当N=500时有多少条路。
我们来用DP的思想来解决这个问题x
设矩阵是$A[N][N]$.
假设我们已经知道了最大路径，并且经过（x, y）这个位置，为了从起点到终点得到的和最大，那么从起点到 (x , y) 经过的数的和也一定要最大。这几乎是显然的。
这是理解这一题的重点。
走到 (x, y) 的上一步，可能是 （x-1, y） 或者（x, y-1）.
按照我门上面得出的结论，我们可以这样说：
如果从起点达到(x,y)的最优路径要经过(x – 1,y)或者(x,y – 1)则，从起点到达(x – 1,y)或者(x,y – 1)的路径一定也必须是最优的。
所以只需要比较 到达(x – 1,y)或者(x,y – 1)的最优路径哪一个更加优。为了方便表示，我们用：
$f(x, y)$ 来表示起点到 （x，y）的最优路径长度。
所以,起点到 （x，y）的最优路径可以表示成：
$$f(x, y) = max(f(x-1, y) , f(x, y-1)) + A[x][y]$$
到了这里肯定会有疑问了，这怎么感觉和上面的贪心策略差不多？？
其实不，这里是理解DP的重点。根据上面的这个递推公式，我门可以准确的推导出从起点到所有点的最优解。是整体的最优。而贪心策略只是在局部做选择，是局部的最优。
这里需要好好思考！
注意：最优路径不一定是唯一的。
把整个矩阵遍历一遍就能推导出答案。
代码：
请同学们自己思考一下，写写。
#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 500+10;
int a[MAXN][MAXN];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
for (int i = 1; i < n; i++)
{
a[0][i] += a[0][i-1];
a[i][0] += a[i-1][0];
}
for (int i = 1; i < n; i++)
for (int j = 1; j < n; j++)
a[i][j] += max(a[i-1][j], a[i][j-1]);
cout << a[n-1][n-1] << endl;
return 0;
}
例题2：
2.最大字段和问题
给出一个整数数组a(正负数都有)，最多有50000个，如何找出一个连续子数组（可以一个都不取），使得其中的和最大？
例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。
这个问题的暴力解决方案就是一个双层循环，$O(N^2)$ 时间复杂度，50000个数据一定超时。
for(int i = 1; i <= n; i++)
{
int sum = 0;
for(int j = i; j <= n; j++)
{
sum += a[j];
ans = max(ans, sum);
}
}
这已经是可以用动态规划思想去考虑的最简单的问题了，
每一步的决策无非就是，是否继续把下一个元素加入当前的子段.
动态规划大显身手。我们开一个数组dp[] , 记录dp[i]表示以a[i]结尾的 全部子段中 最大的那个的和。
这样我们就可以根据它dp[i] 的正负，去考虑是否把下一个元素加入到当前的子段。
如果dp[i] 是负数，那么我们为什不从a[i+1]新维护一个子段呢？
如果dp[i] 是正数，那么显然可以继续把a[i+1] 加入到当前的子段。
最后我们只需要找出所有最大子段中，最大的那个。
代码：
#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 50000+10;
long long a[MAXN];
int main()
{
int n;
long long ans;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
ans = a[0];
for (int i = 1; i < n; i++)
{
if (a[i-1] > 0)
a[i] += a[i-1];
ans = max(ans, a[i]);
}
cout << ans << endl;
return 0;
}
例题3：
[3.最长公共子序列]
简称（LCS）（Longest common subsequence）
给出两个字符串，最长长度是1000，求它们的LCA。
首先要解释一下子序列和子串的区别，序列是不一定连续的，串是必须连续的。
比如，一个字符串：123456
子序列： 1 4 125 2456
子串： 2 5 123 2345
对于一个长度为n的序列，它一共有$(2^n – 1)$个非空子序列。
如此大多的情况显然不能暴力
最长公共子序列的长度一定，但是序列不唯一。
为了方便我们来定义几个变量
两个序列： A, B
A[0]～A[x]: Ax
B[0]～B[y]: By
Ax和By的LCS的长度：$f(x,y)$
让我们来看看如何求$f(x, y)$。x,y表示子序列考虑最后一项
（1） A[x] ＝ B[y]
那么它们$f(x, y)$的最后一项一定是这个元素！
因此$f(x, y) = f(x - 1, y - 1)$ 最后接上这个元素
$$f(x, y) = f(x - 1, y - 1) + 1$$
（2） A[x] !＝ B[y]
$f(x,y) == f(x-1, y-1) ?$
并不是。比如两个序列：
01
12
如果$f(x,y) == f(x-1, y-1)$ , 那么$f(1, 1) = f (0,0) = 0$ . 显然是错误的。
因为虽然 A[x] !＝ B[y] ，但是可能 A[x] = B[y-1] 或者 A[x-1] = B[y].
所以 $f(x,y) == f(x-1, y) $或者是$f(x, y-1)$
$$f(x,y) = \begin{cases}
f(x-1,y-1)+1 & A[x]= B[y] \
max(f(x-1,y), f(x,y-1)) & A[x]!=B[y]
\end{cases}$$
如何输出路径？
计算长度的时候只要多记录一些信息，就可以利用这些信息恢复出一个最长公共子序列来。就好比我们在迷宫里走路，走到每个位置的时候记录下我们时从哪个方向来的，就可以从终点回到起点一样。
例题4：
4.编辑距离
给定两个字符串S和T，对于T我们允许三种操作：
(1) 在任意位置添加任意字符
(2) 删除存在的任意字符
(3) 修改任意字符
问最少操作多少次可以把字符串T变成S？
例如： S＝ “ABCF” T = “DBFG”
那么我们可以
(1) 把D改为A
(2) 删掉G
(3) 加入C
所以答案是3。
给定字符串S和T，我们可以用特殊字符促成对齐。我们加的特殊字符是“-”, 最终两个串相同位置出现了不同字符，就扣1分，我们要使得这两个串对齐扣分尽量少。
对于例子 我们实际上采取了这样的对齐方式：
ABCF-
DB-FG
我们设$f(i,j)$表示S的前i位和T的前j位对齐后的最少扣分。
(1) S[i] = T[j], 前i – 1和j – 1位已经对齐。这种情况下最少的扣分是$f(i-1,j-1)$
(2) S[i] ≠ T[j]，这种情况下最少的扣分是$f(i -1, j – 1) + 1$ 。或：
(3) S的前 i 位和T的前（j – 1）位已经对齐了。这种情况下最少的扣分是$f(i,j-1) + 1$ ，或：
(4) S的前(i-1)位已经和T的前j位对齐了。这种情况下最少的扣分是$f(i,j-1) + 1$
每一个$f(i,j)$都是从上面的四中情况推导出
具体取什么值，显然是要看哪种情况的扣分最少。
$$f(i,j) = min(f(i – 1, j – 1) + same(i,j), f(i – 1,j ) + 1, f(i, j – 1) + 1)$$
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
const int MAXN = 1000+1;
const int INF = 0x3f3f3f3f;
int dp[MAXN][MAXN];
int same(int a, int b)
{
if (a == b)
return 0;
else return 1;
}
int main()
{
int len1, len2;
string s1, s2;
cin >> s1 >> s2;
s1 = " " + s1, s2 = " " + s2;
len1 = s1.length();
len2 = s2.length();
for (int i = 0; i < len1; i++)
dp[0][i]=i;
for (int i = 0; i < len2; i++)
dp[i][0]=i;
for (int i = 1; i < len1; i++)
for (int j = 1; j < len2; j++)
dp[i][j] = min(dp[i-1][j-1]+same(s1[i],s2[j]),min(dp[i-1][j]+1, dp[i][j-1]+1));
cout << dp[len1-1][len2-1] << endl;
return 0;
}
例题5：
5.最长递增子序列
给你一个序列，最多有50000个。问最长递增子序列有多长。
子序列不一定是连续的。
for (int i = 1; i < n; i++)
{
for (int j = 0; j <= ans; j++)
{
if (j >= ans)
{
dp[j] = a[i], ans++;
break;
}
else if (dp[j] > a[i])
{
dp[j] = a[i];
break;
}
}
}
这是个$N^2$的算法，肯定会超时.。下面的代码优化到$NlogN$。
for(int i = 1;i < n;i ++)
{
if(a[i] > dp[ans - 1])
dp[ans ++] = a[i];
else
b[binarySearch(a[i])] = a[i];
}
Comments | NOTHING