动态规划总结【模板】

作者:网络    软件教程库   2020-05-14

最长递增子序列

给定一个序列,找到最长子序列的长度,使得子序列中的所有元素被排序的顺序增加。

1.求最长递增子序列的长度o(n^2)

int arr[30010],list[30010];
int lis(int *arr,int n)    //arr[]存放的是待求数组
{
    int max = 0;        //max为最大递增子序列的长度
    for(int i = 1; i = n; ++i)
        list[i] = 1;    //lis[i] 存放i之前的最大递增子序列的长度,初始都为1

    for(int i = 2; i = n; ++i)
        for(int j = 1; j  i; ++j)    //遍历i之前所有位置
            if(arr[i] = arr[j]  list[i]list[j]+1)
                list[i] = list[j] + 1;
            //arr[i]arr[j]为递增
            //lis[i]lis[j] + 1确保为当前最长递增序列

    for(int i = 1; i = n; ++i)
        if(max  list[i])
            max = list[i];

    return max;
}

2.求最长递增子序列的长度o(nlogn)

int arr[10010],list[10010];
int stack[10010];
int lis(int *arr,int n)
{
    int top = 0;
    stack[top] = -1;
    for(int i = 1; i = n; ++i)
    {
        if(arr[i]  stack[top])
            stack[++top] = arr[i];
        else
        {
            int low = 1;
            int high = top;
            while(low = high)
            {
                int mid = (low + high)/2;
                if(arr[i]  stack[mid])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            stack[low] = arr[i];
        }
    }
    return top;
}

最长公共子序列

给定两个序列,找出在两个序列中同时出现的最长子序列的长度。一个子序列是出现在相对顺序的序列,但不一定是连续的。

1.求最长公共子序列长度

char s1[220],s2[220];
int dp[220][220];
//求串s1和串s2的公共子序列
int lcs(char *s1,char *s2)
{
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    for(int i = 0; i = len1; ++i)
    {
        for(int j = 0; j = len2; ++j)
        {
            if(i == 0 || j == 0)
                dp[i][j] = 0;
            else if(s1[i-1] == s2[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[len1][len2];
}

2.求最长公共子序列长度,并输出路径

int dp[110][110],pre[110][110],len1,len2;
char s1[110],s2[110];

void lcs(char *s1,char *s2)
{
    for(int i = 0; i = len1; ++i)
        pre[i][0] = 1;
    for(int i = 0; i = len2; ++i)
        pre[0][i] = 2;
    //得到最长公共子序列,并标记dp[i][j]的上一个状态,用来回溯寻找路径
    for(int i = 0; i = len1; ++i)
    {
        for(int j = 0; j = len2; ++j)
        {
            if(i == 0 || j == 0)
                dp[i][j] = 0;
            if(s1[i-1] == s2[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
                pre[i][j] = 0;
            }
            else if(dp[i-1][j] = dp[i][j-1])
            {
                dp[i][j] = dp[i-1][j];
                pre[i][j] = 1;
            }
            else
            {
                dp[i][j] = dp[i][j-1];
                pre[i][j] = 2;
            }
        }
    }
}

void print(int i,int j) //回溯输出新的字符串序列
{
    if(i == 0  j == 0)
        return ;
    if(pre[i][j] == 0)
    {
        print(i-1,j-1);
        printf("%c",s1[i-1]);
    }
    else if(pre[i][j] == 1)
    {
        print(i-1,j);
        printf("%c",s1[i-1]);
    }
    else
    {
        print(i,j-1);
        printf("%c",s2[j-1]);
    }
}

void solve(char *s1,char *s2)
{
    len1 = strlen(s1);
    len2 = strlen(s2);
    lcs(s1,s2);
    print(len1,len2);
    printf("\n");
}

最长回文子序列

给一个字符串,找出它的最长的回文子序列lps的长度。例如,如果给定的序列是“bbabcbcab”,则输出应该是7,“babcbab”是在它的最长回文子序列。

char s[2020];
int dp[2020][2020];
//dp[i][j]表示s[i~j]最长回文子序列
int lps(char *s)
{
    memset(dp,0,sizeof(dp));
    int len = strlen(s);
    for(int i = len-1; i = 0; --i)
    {
        dp[i][i] = 1;
        for(int j = i+1; j  len; ++j)
        {
            if(s[i] == s[j])    //头尾相同,最长回文子序列为去头尾的部分lps加上头和尾
                dp[i][j] = dp[i+1][j-1] + 2;
            else    //头尾不同,最长回文子序列是去头部分的lps和去尾部分lps较长的
                dp[i][j] = max(dp[i][j-1],dp[i+1][j]);
        }
    }

    return dp[0][len-1];
}

最小编辑距离

给定一个长度为m和n的两个字符串,设有以下几种操作:替换(r),插入(i)和删除(d)且都是相同的操作。寻找到转换一个字符串插入到另一个需要修改的最小(操作)数量。

int dp[1010][1010],len1,len2;
char s1[1010],s2[1010];
int editdist(char *s1,char *s2)
{
    int len1 = strlen(s1);
    int len2 = strlen(s2);
//当两个字符串的大小为0,其操作距离为0。
//当其中一个字符串的长度是零,需要的操作距离就是另一个字符串的长度. 
    for(int i = 0; i = len1; ++i)
        dp[i][0] = i;
    for(int i = 0; i = len2; ++i)
        dp[0][i] = i;

    for(int i = 1; i = len1; ++i)
    {
        for(int j = 1; j = len2; ++j)
        {
            if(s1[i-1] == s2[j-1])  //对齐s1[i-1]和s2[j-1],不需改变
                dp[i][j] = dp[i-1][j-1];
            else    
                dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1])) + 1;
            //s1前缀右对齐,s2前缀右为‘ ‘,删除s1第i个字符 - dp[i-1][j]
            //s2前缀右对齐,s1前缀右为‘ ‘,删除s2第j个字符 - dp[i][j-1]
            //s1前缀右对齐,s2前缀右对齐,i、j不一样,替换 - dp[i-1][j-1]
        }
    }
    return dp[len1][len2];
}

动态规划总结【模板】

原文地址:http://blog.csdn.net/lianai911/article/details/45424703

软件教程库 原文地址:https://www.itjcku.com/9999/1091408.html

阅读全部内容


Tags:动态规划计划总结模板

返回首页



推荐内容

HDUACM1103Flo'sRestaurant

分析:借助stl的min_element实现。每次更新最先被占用的桌子,具体见注释。 #includelt;iostre ...

【翻译自mos文章】Oracledb12c中,每次日志切换时,会改变alert_sid.log的权限

12c中,每次日志切换时,会改变alert_sid.log的权限 来源于: alert log file‘s perm ...

poj1988(并查集)

题意:有30000个木块,编号从1到30000,然后有两种操作m a b,把木块a所在的堆块放到木块b所在的堆块上,操作 ...

org.hibernate.exception.GenericJDBCException:Couldnotopenconnection

1、错误描述 org.hibernate.exception.genericjdbcexception: could ...

ubuntu下mysql导出数据

使用的是workbench,原因时workbench的导出工具mysqldump和mysql的版本不一致,这个时候手动指 ...

怎样看懂女人哪些最直接的肢体暗示,撒娇

主动拥抱。 拥抱是最简单却十分亲密的身体接触,女人在想亲热时,会主动寻求拥抱,向伴侣靠近。如果她躺在你的怀抱中,并用语言 ...

移动后端云平台Bmob介绍

对于移动端的独立开发者来说,最痛苦的事情莫过于搭建后台服务器。没有基础的还得从头学起,有技术的又要搭建维护后台,非常 ...

WAMP配置虚拟主机

问题背景:从网上下载了一个php项目a,a项目需要部署在网站的根目录下。配置虚拟主机可以解决这个问题。1.打开apach ...

java克隆测试

1.person类 1 //clone方法必须实现cloneable接口 2 public class perso ...

C++string中用于查找的find系列函数浅析

总述:以下所讲的所有的string查找函数,都有唯一的返回类型,那就是size_type,即一个无符号整数(按打印出来的 ...

Savingoutputofagrepintoafilewithcolors

19 down vote favorite 7 i need to save the result o ...

hibernate异常之QueryException

org.hibernate.queryexception: expected positional parameter ...

Redis的Python客户端redis-py的初步使用

1. 安装 sudo pip install redis sudo pip install hiredis pa ...

《构建高性能Web站点》笔记

书名:构建高性能web站点 出版社: 电子工业出版社 isbn:9787121170935 一 绪论 等待的时间: ( ...

制作OSX10.10.3启动安装U盘

1.获得install os xyosemite.app 2.准备一个8gb的u盘,用磁盘工具抹掉,格式默认的mac o ...

域名解析URL转发

url转发 转发功能:如果您没有一台独立的服务器(也就是没有一个独立的ip地址)或者您还有一个域名b,您想访问a域名时访 ...

instancetypeVSid

英文好的直接读下面链接的文章就好了: http://stackoverflow.com/questions/897222 ...

androidapp开发感想

这几天帮学长做app的时候,照着视频学了json数据的传递,接着遇到了问题,就是httpurlconnection会 ...

常用软件及注册码

vmware-workstation-full-11.0.0-2305329.exe m50ac-j034j-08l8a ...

[POJ3420]QuadTiling

quad tiling time limit:1000ms memory limit:65536k to ...

C-关键字,标识符,注释

一.关键字:c语言中提供了有特殊含义的符号,也叫做保留字。 c语言中一个32个关键字,这些关键字都被赋予了 ...

C-基本概念

一.程序结构 1.c 程序结构:任何一个c程序都是由一个或小个程序代码块组成,每个小程序都有自己的功能,一般称这些小 ...

应该具备的能力

1. 学习能力(learning ability)   有些东西不懂很正常,从不懂到懂,从懂到精通,自己想想,原来不会的 ...

Apache-rhel5.8环境下编译安装

apache安装过程 step 1:安装包gcc或gcc-c++# yum install gcc#yum insta ...

OpenWrt学习目标

最近在研究openwrt,总感觉这一看一点那也了解一点,没有目的,也没有重心。 这里,给自己拟定一个目标,就朝着这个目标 ...

HelloKiki(hdu3579+不互质的中国剩余定理)

hello kiki time limit:1000msmemory limit:32768kb64bit io ...

android环境下摄像头数据采集及显示

以前项目涉及些摄像头预览及数据处理操作,当时的需求是除了做摄像头预览外,还要显示文字、个性图像等,当初在查找资料实 ...

uva10003CuttingSticks简单区间dp

// uva 10003 cutting sticks 区间dp // 经典的区间dp // dp(i,j)表示切割小木 ...

Go的语言特性总结

写在前面: 近来关于对golang的讨论有很多,七牛的几个大牛们也断定go语言在未来将会快速发展,并且很可能会取代ja ...

golang控制channel的出入口

golang控制channel的出入口 我们常常使用channel来在多个goroutine之间做数据通讯,但是cha ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com