文档章节

教你彻底学会动态规划——进阶篇

H
 Henrykin
发布于 2017/03/28 11:16
字数 1956
阅读 11
收藏 0

 在我的上一篇文章中已经详细讲解了动态规划的原理和如何使用动态规划解题。本篇文章,我将继续通过例子来让大家更加熟练地使用动态规划算法。

    话不多说,来看如下例题,也是在动态规划里面遇到过的最频繁的一个题,本题依然来自于北大POJ:

    最长公共子序列(POJ1458)

    给出两个字符串,求出这样的一个最长的公共子序列的长度:子序列中的每个字符都能在两个原串中找到, 而且每个字符的先后顺序和原串中的先后顺序一致。

    Sample Input

    abcfbc abfcab

    programming    contest

    abcd    mnp

    Sample Output

    4

    2

    0

    解题思路:设输入的两个串为s1,s2, 设MaxLen(i,j)表示::s1的左边i个字符形成的子串,与s2左边的j个字符形成的子串的最长公共子序列的长度(i,j从0 开始算),则MaxLen(i,j) 就是本题的“状态” (如果还不懂“状态”是什么意思,可以参考我上一篇文章)

    假定 len1 = strlen(s1),len2 = strlen(s2),那么题目就是要求   MaxLen(len1,len2)

    显然:

    MaxLen(n,0)  = 0  ( n= 0…len1)

    MaxLen(0,n)  = 0  ( n=0…len2)

    于是,我们可以得到如下的递推公式:  

  1. if ( s1[i-1] == s2[j-1] ) //s1的最左边字符是s1[0]     
        MaxLen(i,j) = MaxLen(i-1,j-1) + 1;   
    else    
        MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) );   

     

    时间复杂度O(mn) m,n是两个字串长度

    

    S1[i-1]!= s2[j-1]时,MaxLen(S1,S2)不会比MaxLen(S1,S2j-1) 和MaxLen(S1i-1,S2)两者之中任何一个小,也不会比两者都大。

    通过上面的分析,我们很简单就可以写出如下的代码:  

  1. #include <iostream>   
    #include <cstring>   
    using namespace std;   
      
    char sz1[1000];   
    char sz2[1000];   
    int maxLen[1000][1000];   
    int main(){    
        while( cin >> sz1 >> sz2 ) {     
            int length1 = strlen( sz1);     
            int length2 = strlen( sz2);     
            int nTmp;     
            int i,j;     
            for( i = 0;i <= length1; i ++ )      
                maxLen[i][0] = 0;     
            for( j = 0;j <= length2; j ++ )      
                maxLen[0][j] = 0;   
            for( i = 1;i <= length1;i ++ ) {      
                for( j = 1; j <= length2; j ++ ){       
                    if( sz1[i-1] == sz2[j-1] )            
                        maxLen[i][j] =  maxLen[i-1][j-1] + 1;       
                    else             
                        maxLen[i][j] = max(maxLen[i][j-1],maxLen[i-1][j]);      
                }     
            }     
            cout <<  maxLen[length1][length2] << endl;    
        }    
        return 0;    
    }   

     

    然后提交我们的代码,一次AC。

    

   

    接下来我们再来看一道典型的例题:

    最长上升子序列(百练2757)

    一个数的序列ai,当a1 < a2 < ... < aS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN),我们可以得到一些上升的子序列(ai1, ai2, ..., aiK),这里1 <= i1 < i2 < ... < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8), 有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8).。

    你的任务,就是对于给定的序列,求出最长上升子序列的长度。

    输入数据

    输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000。

    输出要求

    最长上升子序列的长度。

    输入样例

    7

    1 7 3 5 9 4 8

    输出样例

    4

    解题思路

    1.找子问题

    “求序列的前n个元素的最长上升子序列的长度”是个子问题,但这样分解子问题,不具有“无后效性”,因为假设F(n) = x,但可能有多个序列满足F(n) = x。有的序列的最后一个元素比 an+1小,则加上an+1就能形成更长上 升子序列;有的序列最后一个元素不比an+1小……以后的事情受如何达到状态n的影响,不符合“无后效性” ,因此我们必须换一种思路来解决此问题。

    “求以ak(k=1, 2, 3…N)为终点的最长上升子序列的长度”,一个上升子序列中最右边的那个数,称为该子序列的 “终点”。虽然这个子问题和原问题形式上并不完全一样,但是只要这N个子问题都解决了,那么这N个子问题的解中, 最大的那个就是整个问题的解。

    2.确定状态

    子问题只和一个变量—— 数字的位置相关。因此序列中数的位置k就是“状态”,而状态 k 对应的“值”,就是以ak做为“终点”的最长上升子序列的长度。 状态一共有N个。

    3.找出状态转移方程

     maxLen (k)表示以ak做为“终点”的

    最长上升子序列的长度那么:

    初始状态:maxLen (1) = 1

    maxLen (k) = max { maxLen (i):1<=i < k 且 ai < ak且 k≠1 } + 1      

     若找不到这样的i,则maxLen(k) = 1

    maxLen(k)的值,就是在ak左边,“终点”数值小于ak ,且长度最大的那个上升子序列的长度再加1。因为ak左边任何“终点”小于ak的子序列,加上ak后就能形成一个更长的上升子序列。

    有了这个思路,我们就可以很轻松地写出代码了。然而,即使到了这里,我们依然还能从两个方向解决这道题,我们可以将它们分别称为“人人为我”递推型动归和“我为人人”递推型动归 。请看下面的讲解:

    “人人为我”递推型动归

    状态i的值Fi由若干个值 已知的状态值Fk,Fm,..Fy 推出,如求和,取最大值

    

    根据这个方向,我们不难写出如下代码:  

  1. #include <iostream>   
    #include <cstring>   
    #include <algorithm>   
    using namespace std;   
      
    const int  MAXN =1010;   
    int a[MAXN];   int maxLen[MAXN];   
      
    int main(){     
        int N;     
        cin >> N;    
        for( int i = 1;i <= N;++i){     
            cin >> a[i];     
            maxLen[i] = 1;    
        }    
        for( int i = 2; i <= N; ++i){ //每次求以第i个数为终点的最长上升子序列的长度     
            for( int j = 1; j < i; ++j)  //察看以第j个数为终点的最长上升子序列      
                if( a[i] > a[j] )       
                    maxLen[i] = max(maxLen[i],maxLen[j]+1);     
        }    
        cout << * max_element(maxLen+1,maxLen + N + 1 );    
        return 0;   
    } //时间复杂度O(N2)  
    

     

    下面是我这段代码的提交结果:

    

    “我为人人”递推型动归

    状态i的值Fi在被更新(不一定是 最终求出)的时候,依据Fi去更 新(不一定是最终求出)和状态i 相关的其他一些状态的值 Fk,Fm,..Fy

    

    根据这个方向,我们又可以写出如下代码:  

  1. #include <iostream>   
    #include <cstring>   
    #include <algorithm>   
    using namespace std;   
      
    const int  MAXN =1010;   
    int a[MAXN];   
    int maxLen[MAXN];     
      
    int main(){     
        int N;     
        cin >> N;    
        for( int i = 1;i <= N;++i){     
            cin >> a[i];     
            maxLen[i] = 1;    
        }    
        for( int i = 1; i <= N; ++i)      
            for( int j = i + 1; j <= N; ++j )  //看看能更新哪些状态的值      
                if( a[j] > a[i] )       
                    maxLen[j] = max(maxLen[j],maxLen[i]+1);    
        cout << * max_element(maxLen+1,maxLen + N + 1 );    
        return 0;  
    } //时间复杂度O(N2)   
    

     

    下面是我这段代码的提交结果:

    

 

    接下来,就要进行一个总结了:

    动规的三种形式

    1)记忆递归型

    优点:只经过有用的状态,没有浪费。递推型会查看一些 没用的状态,有浪费。

    缺点:可能会因递归层数太深导致栈溢出,函数调用带来额外时间开销。总体来说,比递推型慢。

    2) “我为人人”递推型

    没有什么明显的优势,有时比较符合思考的习惯。个别特殊题目中会比“人人为我”型节省空间。

    3)“人人为我”递推型

    在选取最优备选状态的值Fm,Fn,…Fy时, 有可能有好的算法或数据结构可以用来显 著降低时间复杂度。



版权声明:本文为博主原创文章,未经博主允许不得转载。

本文转载自:http://blog.csdn.net/baidu_28312631/article/details/47426445

H
粉丝 4
博文 102
码字总数 12788
作品 0
广州
私信 提问
Android自定义控件三部曲文章索引

前言:在我从C++转到Android时,就被Android里炫彩斑斓的自定义控件深深折服,想知道如果想利用C++实现这些功能,那是相当困难的。从那时候起,我就想,等我学会了自定义控件,一定要写一篇系...

丁佳辉
2016/04/13
110
0
爬虫系列的总结

图片来自 unsplash 时光荏苒,四个月时间如流沙般从手心中流逝。这四个月自己算是收获颇多。因为在张哥的影响下,自己渐渐喜欢上写作。自己将所学的爬虫知识、学习心得以及如何学习分享出来。...

猴哥Yuri
2017/10/27
0
0
ACM进阶计划

ACM进阶计划 ACM队不是为了一场比赛而存在的,为的是队员的整体提高。 大学期间,ACM队队员必须要学好的课程有: l C/C++两种语言 l 高等数学 l 线性代数 l 数据结构 l 离散数学 l 数据库原理...

angel_kitty
2017/04/19
0
0
只需几步即可提升你的 SQL 技能

如果你习惯了使用 ActiveRecord 或者 SQLAlchemy,当你需要编写 SQL 的时候就会茫然失措,但,并不是只有你一个人会这样。 只需要一些时间来练习,你就可以像专家一样编写高级的查询。 坚实的...

OSC编辑部
2015/08/05
2.2K
9
Java互联网四大项目开发案例教学,阿里天猫核心技术首次公布!

Java互联网四大项目开发案例教学,阿里天猫核心技术首次公布! 阶段一 初级项目阶段 技术性点 项目范例 1)视频播放器 — 成功视频播放器4大基本功能和播放列表8大基本功能,熟练掌握集合和 ...

Java小仙女
02/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

读书笔记:深入理解ES6 (五)

第五章 解构:使数据访问更便捷 第1节 为什么使用解构功能?   在ES5中,开发者们从对象、数组中获取特定数据并赋值给变量,编写了很多看起来同质化的代码。例如: 1 let options = {2 ...

张森ZS
16分钟前
15
0
CentOS7 yum方式安装MySQL5.7

在CentOS中默认安装有MariaDB,这个是MySQL的分支,但为了需要,还是要在系统中安装MySQL,而且安装完成之后可以直接覆盖掉MariaDB。 1 下载并安装MySQL官方的 Yum Repository [root@localho...

roockee
24分钟前
11
0
Allegro三种自定义设置快捷键的方法

Allegro自定义设置快捷键的三种方法: 1、在Allegro PCB editor 命令窗口直接定义 2、通过修改用户变量env文件来设置快捷键 3、定义笔画为快捷键 1、在Allegro PCB editor 命令窗口直接定义 ...

demyar
29分钟前
14
0
如何做一张能让人眼前一亮的大屏?

作为在职场驰骋的社会人,提到数据可视化大家应该都不陌生了。数据可视化的作用也不用我多说,主要是利用图形化手段,更清晰直观地将数据展示。多层次、交互式的可视化分析能够方便决策者理解...

朕想上头条
29分钟前
7
0
TL138/1808/6748-EthEVM开发板硬件CPU、FLASH、RAM

TL138/1808/6748-EthEVM是广州创龙基于SOM-TL138/1808/6748核心板开发的一款开发板,具有三个网络接口。由于SOM-TL138/1808/6748核心板管脚兼容,所以此三个核心板共用同一个底板。开发板采用...

Tronlong创龙
34分钟前
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部