动态规划入门

发布于 2019-07-27  1.9k 次阅读


动态规划入门


简单介绍

动态规划(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];
}

Simple And Clear