文档章节

动态规划套路在最长公共子串、最长公共子序列和01背包问题中的应用

realsa
 realsa
发布于 2016/10/01 22:56
字数 1976
阅读 108
收藏 0

适合动态规划(DP,dynamic programming)方法的最优化问题有两个要素:最优子结构和重叠子问题。

最优子结构指的是最优解包含的子问题的解也是最优的。

重叠子问题指的是每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。

所以可以用如下步骤来解决:

  1. 递归定义最优解计算公式
  2. 构造dp矩阵,按照公式逐步计算。

接下来我们分别在最长公共子串、最长公共子序列和01背包问题中演示如何应用上面的套路。

开始讨论之前要明白子串和子序列的区别在于:子串要求在原字符串中是连续的,而子序列则没有要求[1]。例如, 字符串 s1=abcde,s2=ade,则LCStr=de,LCSeq=ade。

其中LCStr表示Longest Common Substring 。LCSeq表示Longest Common Subsequence。

1 最长公共子串

问题定义

对于两个字符串,请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度),求出两串的最长公共子串的长度。 给定两个字符串A和B,同时给定两串的长度n和m。

测试样例:"1AB2345CD",9,"12345EF",7

返回:4

1.1 递归公式

假设有字符串x,y

f(i,j)表示x中以x[i]结尾的子串集合和y中以y[j]结尾的子串集合,两者交集中最长串的长度。(i和j都在合法范围内)

比如x="caba",以a[2]结尾的子串集合如下: { "b","ab","cab"}

当x[i]!=y[j]时,毫无疑问,交集为空集,此时f(i,j) = 0

当x[i]==y[j]时,f(i,j) = f(i-1,j-1) + 1

当i=0或者j=0时,f(i,j) = 0 //递归出口,边界情况

1.2 dp矩阵

有了递归公式就可以设计dp表格了,假设x="caba" , y="bab" , 二维数组dp[i][j]对应f(i,j)。当x[i]==y[j]时,dp[i][j]=dp[i-1][j-1]+1

从左到右,从上到下计算得到dp表格:

同样的本题的dp表格如下

1.3 AC代码

class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        //初始化n*m matrix
        vector<vector<int> > dp(n,vector<int>(m,0));
        int res=0;
        for(int i=0;i<n;i++)//x串
        {
            for(int j=0;j<m;j++)// y串
            {
                if(A.at(i)==B.at(j))
                {
                    if(i==0||j==0)  dp[i][j]=1;
                    else    dp[i][j]=dp[i-1][j-1]+1;
                    // udpate maximum
                    if(res<dp[i][j]) res=dp[i][j];
                }
            }
        }
        return res;
    }
};

2 最长公共子序列LCS

问题定义

对于两个字符串,请设计一个高效算法,求他们的最长公共子序列的长度, 这里的最长公共子序列定义为:有字符串A的下标序列U1,U2,U3...Un和字符串B的下标序列V1,V2,V3...Vn,其中Ui < Ui+1,Vi < Vi+1。且A[Ui] == B[Vi]。

给定两个字符串A和B,同时给定两个串的长度n和m,请返回最长公共子序列的长度。保证两串长度均小于等于300。

测试样例:"1A2C3D4B56",10,"B1D23CA45B6A",12

返回:6

2.1 递归公式

假设有字符串x和y, 这里我们用x[0,i]来表示x中下标为[0,i]的子串切片,对应于python中的x[0:i+1]。比如x="abcdea",那么x[0,1]就表示"ab"。

定义f(i,j)表示x[0,i]和y[0,j]之间的最长公共子序列。

毫无疑问我们又要想办法用f(i-1,j-1)来表示f(i,j)。

当x[i]==y[j]时,f(i,j) = f(i-1,j-1) +1

当x[i]!=y[j]时,f(i,j) = max( f(i-1,j) , f(i,j-1) )

同样的为保证f()参数合法,当参数小于0时,返回值为0。

当i<0或者j<0时,f(i,j)=0 //递归出口

这不难理解,比如f(0,0)实际上比较的是x[0]和y[0]两个字符的最长公共子序列,无非是0或者1。

而f(-1,2)中参数-1表示x取一个空串,y取y[0,2]。空串和任何字符串的LCS毫无疑问都是0

2.2 dp矩阵

以x="abcdea",y="aebcda"为例,构造dp表格如下:

2.3 AC代码

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        vector<vector<int> > dp(n,vector<int>(m,0));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(A[i]==B[j]){                    
                    int t=0;
                    if(i-1>=0 && j-1>=0) t=dp[i-1][j-1];
                    dp[i][j]=t+1;
                }                    
                else{                    
                    int t1=0;
                    int t2=0;
                    if(i-1>=0) t1=dp[i-1][j];
                    if(j-1>=0) t2=dp[i][j-1];
                    dp[i][j]=max(t1,t2);
                }
            }
        }
        //右下角
        return dp[n-1][m-1];
    }
};

这里需要考虑的边界情况较多,为简化代码,可以考虑字符串从1开始数

dp[i][j]就表示x[0,i-1]和y[0,j-1]的最长公共子序列

对应递归公式[1]:

这样的dp矩阵,字符串的下标和矩阵的行号列号会有些错位:

不需要判断越界问题,代码精简,但是不好理解

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
         //(n+1)*(m+1)
        vector<vector<int> > dp(n+1,vector<int>(m+1,0));       
        //按照dp的index来填充矩阵
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {                
                if(A[i-1]==B[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[n][m];
    }
};

//或者

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        vector<vector<int> > dp(n+1,vector<int>(m+1,0));    
        //按照string的索引来填充dp矩阵
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(A[i]==B[j]) dp[i+1][j+1]=dp[i][j]+1;
                else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
            }
        }
        return dp[n][m];
    }
};

3 01背包问题

问题定义[2]

话说有一哥们去森林里玩发现了一堆宝石,他数了数,一共有n个。 但他身上能装宝石的就只有一个背包,背包的容量为C。这哥们把n个宝石排成一排并编上号: 0,1,2,…,n-1。第i个宝石对应的价值和重量分别为V[i]和W[i] 。排好后这哥们开始思考: 背包总共也就只能装下体积为C的东西,那我要装下哪些宝石才能让我获得最大的利益呢?

背包问题分为01背包问题和部分背包问题,区别在于物品是否不可分割。

这里的物品不能分割,讨论的是01背包问题。

假设有1,2,3...n一共n个物品。其中v[i]表示第i个物品价值。w[i]表示第i个物品重量。

d(i,j)表示,要把前i个物品放入背包,背包容量为j

  • 1 递归公式:d(i,j)=

    • 0 //i is 0
    • max( d(i-1,j) , d(i-1,j-w[i])+v[i] ) //j>=w[i] and i>0
  • 2 列表计算

占位

#include<iostream>
#include <stdio.h>
#include<vector>
//#include"fsjtools.h"
using  namespace std;
int main()
{
    int n,c;//number,cap
    while(cin>>n>>c)
    {
        vector<int> w(n+1,0);//weight
        vector<int> v(n+1,0);//value
        for(int i=1;i<=n;i++) cin>>w[i]>>v[i];//start from 1
        //printVector(w);
        //printVector(v);
        vector<vector<int> > dp(n+1,vector<int>(c+1,0));//初始化为0
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=c;j++)
            {
                if(j>=w[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]] + v[i]);
								else dp[i][j]=dp[i-1][j];
            }
        }
        cout<<dp[n][c]<<endl;
    }
}
样例输入

5 10
4 9
3 6
5 1
2 4
5 1

4 9
4 20
3 6
4 20
2 4

5 10
2 6
2 3
6 5
5 4
4 6

样例输出

19
40
15

References

  1. DP:LCS(最长公共子串、最长公共子序列)
  2. 动态规划之背包问题(一)

© 著作权归作者所有

realsa

realsa

粉丝 33
博文 84
码字总数 107087
作品 0
广州
程序员
私信 提问
动态规划 &

一、 动态规划(Dp问题):解决问题的关键点 1) 递推公式:(最有子结构) 2) 数据的初始化 用例分析: a. 01 背包的问题(Knapsack Problem) 定义: 一个背包的容量V; 存在N个物品:w[i...

Playboy002
2015/07/17
57
0
JavaScript 动态规划&贪心算法

原文链接 前言 这一章,我们将介绍另外两种常用的算法:动态规划和贪心算法。动态规划常被人比作是递归的逆过程,而贪心算法在很多求优问题上,是不二之选。下面,我们针对这两种算法,展开详...

Checkson
07/24
0
0
动态规划算法之:最长公共子序列 & 最长公共子串(LCS)

1、先科普下最长公共子序列 & 最长公共子串的区别: 找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。 2、最长公共子串 其实这是一个序贯决...

大数据之路
2013/03/25
53K
2
有趣的算法问题之巧思妙想

有趣的算法 算法之所以有趣,在于他能够化繁为简,他能概括统御世间万物,将一个复杂的问题归结为一个非常简单的问题。其实所有高阶的算法,都可以用两个大的方法去解决,而且屡试不爽。分别...

Nicholas_Jela
2017/09/06
0
0
Algo-Practice: 算法实践(JavaScript & Java),排序,查找、树、两指针、动态规划等

记录一些算法实践 目录 Java篇 一、基础算法 七种基础排序 二叉堆 K选取问题 链表判环问题 N皇后问题 两指针扫描算法举例 位运算(求首个bit1,求bit1的个数,寻找奇数项) 最小栈的实现 横纵有...

qcer
2017/12/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

只需一步,在Spring Boot中统一Restful API返回值格式与统一处理异常

统一返回值 在前后端分离大行其道的今天,有一个统一的返回值格式不仅能使我们的接口看起来更漂亮,而且还可以使前端可以统一处理很多东西,避免很多问题的产生。 比较通用的返回值格式如下:...

晓月寒丶
昨天
59
0
区块链应用到供应链上的好处和实际案例

区块链可以解决供应链中的很多问题,例如记录以及追踪产品。那么使用区块链应用到各产品供应链上到底有什么好处?猎头悬赏平台解优人才网小编给大家做个简单的分享: 使用区块链的最突出的优...

猎头悬赏平台
昨天
28
0
全世界到底有多少软件开发人员?

埃文斯数据公司(Evans Data Corporation) 2019 最新的统计数据(原文)显示,2018 年全球共有 2300 万软件开发人员,预计到 2019 年底这个数字将达到 2640万,到 2023 年达到 2770万。 而来自...

红薯
昨天
65
0
Go 语言基础—— 通道(channel)

通过通信来共享内存(Java是通过共享内存来通信的) 定义 func service() string {time.Sleep(time.Millisecond * 50)return "Done"}func AsyncService() chan string {retCh := mak......

刘一草
昨天
58
0
Apache Flink 零基础入门(一):基础概念解析

Apache Flink 的定义、架构及原理 Apache Flink 是一个分布式大数据处理引擎,可对有限数据流和无限数据流进行有状态或无状态的计算,能够部署在各种集群环境,对各种规模大小的数据进行快速...

Vincent-Duan
昨天
60
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部