今天小编给大家分享一下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数组初始化: //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(int 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,同时也是最适合背的,见过的秒杀，没见过的干瞪眼 //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][j]=fmax(dp[i+1][j],dp[i][j-1]); } } return dp[0][len-1];}以上就是“C++中的动态规划子序列问题怎么解决”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注编程网行业资讯频道。
