动态规划入门
简单介绍
动态规划(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