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數組初始化:
    //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++中的動態規劃子序列問題怎么解決”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。