开发者

C++中的动态规划子序列问题分析探讨

开发者 https://www.devze.com 2023-03-15 10:45 出处：网络 作者： 清风何渡
目录一、子序列(不连续)最长上升子序列最长公共子序列不相交的线二、子序列(连续)最长连续递增序列最长重复子数组最大子序和三、编辑距离判断子序列两个字符串的删除操作不同的子序列编辑距离四、回文回文子串最长回
相关专题：C++动态规划C++动态规划子序列C++子序列问题
目录
  • 一、子序列(不连续)
    • 最长上升子序列
    • 最长公共子序列
    • 不相交的线
  • 二、子序列(连续)
    • 最长连续递增序列
    • 最长重复子数组
    • 最大子序和
  • 三、编辑距离
    • 判断子序列
    • 两个字符串的删除操作
    • 不同的子序列
    • 编辑距离
  • 四、回文
    • 回文子串
    • 最长回文子串

C++中的动态规划子序列问题分析探讨

一、子序列(不连续)

最长上升子序列

经典问题

int lengthOfLIS(int* nums, int numsSize){
    //1.dp[i]表示遍历到nums[i]时，最长递增子序列的长度
    //2.递推式:
    //if(nums[j]<nums[i]) dp[i]=fmax(dp[i],dp[j]+1);
    //3.dp数组初始化:
 php   //dp[i]=1;
    int dp[numsSize];
    for(int i=0;i<numsSize;i++)
        dp[i]=1;
    int ans=1;
    for(int i=1;i<numsSize;i++){
        for(int j=0;j<i;j++){
            if(nums[j]<nums[i]) 
                dp[i]=fmax(dp[i],dp[j]+1);
            ans=fmax(ans,dp[i]);
        }
    }
    return ans;
}

最长公共子序列

经典问题

int longestCommonSubsequence(char * text1, char * text2){
    //1.dp[i][j]表示text1[0...i]与text2[0...j]的最长公共子序列的长度
    //2.递推式:
    //if(text1[i]==text2[j]) dp[i][j]=dp[i-1][j-1]+1;
    //else dp[i][j]=fmax(dp[i-1][j],dp[i][j-1]);
    //3.dp数组初始化:
    //dp[i][0]=dp[0][j]=0;
    int len1=strlen(text1);
    int len2=strlen(text2);
    int dp[len1+1][len2+1];
    for(iISZwOfnt i=0;i<=len1;i++) dp[i][0]=0;
    for(int j=0;j<=len2;j++) dp[0][j]=0;
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(text1[i-1]==text2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else 
                dp[i][j]=fmax(dp[i-1][j],dp[i][j-1]);
        }
    }
    return dp[len1][len2];
}

不相交的线

该问题=求最长公共子序列（数组版本）

int maxUncrossedLines(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int dp[nums1Size+1][nums2Size+1];
    for(int i=0;i<=nums1Size;i++) dp[i][0]=0;
    for(int j=0;j<=nums2Size;j++) dp[0][j]=0;
    for(int i=1;i<=nums1Size;i++){
        for(int j=1;j<=nums2Size;j++){
            if(nums1[i-1]==nums2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=fmax(dp[i-1][j],dp[i][j-1]);
        }
    }
    return dp[nums1Size][nums2Size];
}

二、子序列(连续)

最长连续递增序列

与最长上升子序列相比，多了“连续”这个条件，故只需要比较相邻元素大小即可，不相等dp置为1

int findLengthOfLCIS(int* nums, int numsSize){
    //1.dp[i]表示遍历到nums[i]时，最长连续递增子序列的长度
    //2.递推式:
    //if(nums[i]>nums[i-1]) dp[i]=dp[i-1]+1;
    //3.dp数组初始化:
    //dp[i]=1;
    int dp[numsSize];
    for(int i=0;i<numsSize;i++) dp[i]=1;
    int ans=1;
    for(int i=1;i<numsSize;i++){
        if(nums[i]>nums[i-1])
            dp[i]=dp[i-1]+1;
        ans=fmax(ans,dp[i]);
    }
    return ans;
}

最长重复子数组

与最长公共子序列相比，多了“连续”这个条件，不相等dp置为0

int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int dp[nums1Size+1][nums2Size+1];
    for(int i=0;i<=nums1Size;i++) dp[i][0]=0;
    for(int j=0;j<=nums2Size;j++) dp[0][j]=0;
    int ans=0;
    for(int i=1;i<=nums1Size;i++){
        for(int j=1;j<=nums2Size;j++){
            if(nums1[i-1]==nums2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=0;
            ans=fmax(开发者_开发学习ans,dp[i][j]);
        }
    }
    return ans;
}

最大子序和

很简单，i-1到i时，dp[i]选择dp[i-1]或者不选择

int maxSubArray(int* nums, int numsSize){
    //1.dp[i]表示nums[0...i]中最大子数组和
    //2.递推式:
    //dp[i]=fmax(dp[i-1]+nums[i],nums[i]);
    //3.dp数组初始化:
    //dp[0]=nums[0];
    int dp[numsSize];
    dp[0]=nums[0];
    int ans=dp[0];
    for(int i=1;i<numsSize;i++){
        dp[i]=fmax(dp[i-1]+nums[i],nums[i]);
        ans=fmax(ans,dp[i]);
    }
    return ans;
}

三、编辑距离

判断子序列

这题虽然用暴力法设置两个指针遍历更简单，但是为了训练编辑距离题型的思想，建议从动态规划入手

bool isSubsequence(char * s, char * t){
    //1.dp[i][j]表示遍历到s[i]和t[j]时，两数组的最长公共子序列长度
    //2.递推式:
    //if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1]+dp[i-1]+1;
    //else dp[i][j]=fmax(dp[i-1][j],dp[i][j-1]);
    //3.dp数组初始化:
    //dp[i][0]=dp[0][j]=0;
    int m=strlen(s),n=strlen(t);
    int dp[m+1][n+1];
    for(int i=0;i<=m;i++) dp[i][0]=0;
    for(int j=0;j<=n;j++) dp[0][j]=0;
    for(int 编程客栈i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(s[i-1]==t[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=dp[i][j-1];
        }
    }
    if(dp[m][n]==m) return true;
    else return false;
}

两个字符串的删除操作

这一题理解起来有点吃力，但是好在后面两题都要用，熟能生巧

int minDistance(char * word1, char * word2){
    //1.dp数组的含义:
    //dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，
    //想要达到相等，所需要删除元素的最少次数
    //2.递推式:
    //若word1[i-1]==word2[j-1]:
    //      无需进行删除操作，即删除次数无变化，dp[i][j]=dp[i-1][j-1];
    //若word1[i-1]!=word2[j-1]:
    //      若删除word1[i-1]，问题就变成了dp[i-1][j]基础上加了一次删除操作，dp[i][j]=dp[i-1][j]+1;
    //      若删除word2[j-1]，问题就变成了dp[i][j-1]基础上加了一次删除操作，dp[i][j]=dp[i][j-1]+1;
    //    综上，dp[i][j]=fmin(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
    //3.dp数组初始化:
    //dp[i][0]=i,dp[0][j]=j;
    int m=strlen(word1),n=strlen(word2);
    int dp[m+1][n+1];
    for(int i=0;i<=m;i++) dp[i][0]=i;
    for(int j=1;j<=n;j++) dp[0][j]=j;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(word1[i-1]==word2[j-1])
                dp[i][j]=dp[i-1][j-1];
            else
                dp[i][j]=fmin(dp[i-1][j]+1,dp[i][j-1]+1);
        }
    }
    return dp[m][n];
}

不同的子序列

上题是问删除多少次能使得两字符串相等，这题是问有多少种删除组合能使得两字符串相等，而且这一题只有s这一个字符串需要删除

int numDistinct(char * s, char * t){
    //这题也可以这样问:s最多有多少种删除方法，可以使得s==t
    //1.dp数组的含义:
    //dp[i][j]：以i-1为结尾的字符串s，和以j-1位结尾的字符串t，
    //想要达到相等，s的最多删除组合
    //2.递推式:
    //若s[i-1]==t[j-1]:
    //      s不删，保证s[i-1]和t[j-1]匹配，dp[i][j]=dp[i-1][j-1]];
    //      s也能删，反正s后面多的是有可能和t[j-1]匹配的选手，dp[i][j]=dp[i-1][j];
    //若s[i-1]!=t[j-1]:
    //      s必须删，否则从s[i-1]和t[j-1]开始s和t就不匹配了，dp[i][j]=dp[i-1][j];
    //3.dp数组初始化:
    //dp[i][0]=1;dp[0][j]=0;
    int m=strlen(s),n=strlen(t);
    unsigned long long dp[m+1][n+1];
    for(int i=0;i<=m;i++) dp[i][0]=1;
    for(int j=1;j<=n;j++) dp[0][j]=0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(s[i-1]==t[j-1])
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
            else
                dp[i][j]=dp[i-1][j];
        }
    }
    return dp[m][n];
}

编辑距离

BOSS降临，但其实只要掌握了第2题，这一题也就多了个替换操作

int minDistance(char * word1, char * word2){
    //这题是编辑距离问题的大BOSS,同时也是最适合背的,见过的秒杀，没见过的干瞪眼
    js//1.dp[i][j]表示word1的0~i-1部分转换成word2的0~j-1部分所使用的最少操作数
    //2.递推式:
    //if(word1[i-1]==word2[j-1])-----------等于,无需编辑
    //    dp[i][j]=dp[i-1][j-1];
    //else{
    //    dp=min(
    //      dp[i-1][j]+1,------------------删除word1[i-1],就是在word1[0~i-2]与word2[0~j-1]基础上的操作+1
    //      dp[i][j-1]+1,------------------删除word2[j-1],就是在word2[0~j-2]与word1[0~i-1]基础上的操作+1
    //      dp[i-1][j-1]+1-----------------只需要一次替换操作，就能使问题变成word1[i-1]==word2[j-1]的情况
    //      );
    //}
    //3.dp数组初始化:
    //dp[i][0]=i;dp[0][j]=j;
    int len1=strlen(word1);
    int len2=strlen(word2);
    int dp[len1+1][len2+1];
    for(int i=0;i<=len1;i++) dp[i][0]=i;
    for(int j=1;j<=len2;j++) dp[0][j]=j;
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(word1[i-1]==word2[j-1])
               dp[i][j]=dp[i-1][j-1];
            else{
               int temp=fmin(dp[i-1][j]+1,dp[i][j-1]+1);
               dp[i][j]=fmin(temp,dp[i-1][j-1]+1);
            }
        }
    }
    return dp[len1][len2];
}

四、回文

回文子串

dp[i][j]的取值依赖于dp[i+1][j-1]的取值（即外层依赖于里层）

因此在遍历顺序上也要保证从左下方到右上方，这样才能保证左下方的数据是经过计算的

int countSubstrings(char * s){
    //1.dp[i][j]表示区间范围[i,j]内的字符串是否为回文串
    //2.递推式:
    //若s[i]!=s[j]:
    //      显然,dp[i][j]=false;
    //若s[i]==s[j]:
    //      若j-i<=1: ans++;dp[i][j]=true;
    //      若j-i>1且dp[i+1][j-1]==true:dp[i][j]=true;
    //3.dp数组初始化:
    //dp[i][j]=false;
    //4.dp数组遍历顺序
    //dp[i][j]的取值依赖于dp[i+1][j-1]，则应该从下到上、从左到右
    int len=strlen(s);
    int dp[len][len];
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++)
            dp[i][j]=false;
    }
    int ans=0;
    for(int i=len-1;i>=0;i--){
        for(int j=i;j<len;j++){
            if(s[i]==s[j]){
                if(j-i<=1){
                    ans++;
                    dp[i][j]=true;
                }else if(dp[i+1][j-1]){
                    ans++;
                    dp[i][j]=true;
                }
            }
        }
    }
    return ans;
}

最长回文子串

还是要注意遍历顺序，dp[i][j] 依赖于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，因此，要保证从左下方到右上方遍历，这样才能保证左下方、左方、下方的数据是经过计算的

int longestPalindromeSubseq(char * s){
    //1.dp[i][j]表示字符串在[i,j]范围内的最长回文子序列长度
    //2.递推式:
    //if(s[i]==s[j])
    //    dp[i][j]=dp[i+1][j-1]+2;
    //else
    //    dp[i][j]=fmax(dp[i+1][j],dp[i][j-1]);
    //3.初始化:
    //dp[i][i]=1
    //4.遍历顺序:
    //从下到上、从左到右
    int len=strlen(s);
    int dp[len][len];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<len;i++) dp[i][i]=1;
    for(int i=len-1;i>=0;i--){
        for(int j=i+1;j<len;j++){
            if(s[i]==s[j])
               dp[i][j]=dp[i+1][j-1]+2;
            else
               dp[i][jandroid]=fmax(dp[i+1][j],dp[i][j-1]);
        }
    }
    return dp[0][len-1];
}

到此这篇关于C++中的动态规划子序列问题分析探讨的文章就介绍到这了,更多相关C++动态规划子序列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

0

上一篇:

:下一篇

更多 开发 相关资讯：

精彩评论

暂无评论...
登录 注册
Qedev.com
验证码 换一张
取 消

    关注公众号

    热门标签

    图文推荐

    mysql字符集引起的java.sql.SQLException:Incorrect string value:问题

    mysql字符集引起的java.sql.SQLException:Incorrect string value:问题
    解决Feign异步调用丢失上下文问题

    解决Feign异步调用丢失上下文问题
    一文教会你使用Python来下一场雪

    一文教会你使用Python来下一场雪
    利用python调整Excel行高和列宽的操作示例

    利用python调整Excel行高和列宽的操作示例
    Python字符串检索方式

    Python字符串检索方式
    Android中常见内存泄漏的场景和解决方案详解

    Android中常见内存泄漏的场景和解决方案详解
    python解析网页上的json数据并保存到EXCEL

    python解析网页上的json数据并保存到EXCEL
    使用wxPython创建一个文件夹结构生成器

    使用wxPython创建一个文件夹结构生成器

    开发者开发者网给大家分享系统运维,大数据运维,云计算,编程开发技巧,路由交换,运维和开发相关的资讯及技术文章，同时StackOverflow中文社区，知识经验交流分享。

    法律声明：本站内容均为网友上传，网站举办方负责审核和监督，如存在版权或非法内容，欢迎举报，我们将尽快予以删除。邮箱：devze@qq.com

    Copyright © 2018-2020 开发者. All rights reserved. Powered by 开发者ICP备案号: 京ICP备10032868号-9