欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++中的動(dòng)態(tài)規(guī)劃子序列問(wèn)題分析探討

 更新時(shí)間：2023年03月15日 08:55:05   作者：清風(fēng)何渡  
可能有些讀者有接觸過(guò)動(dòng)態(tài)規(guī)劃，可能也有一些讀者以前完全不知道動(dòng)態(tài)規(guī)劃這個(gè)東西，別擔(dān)心，我這篇文章會(huì)為讀者做一個(gè)入門(mén)，好讓讀者掌握這個(gè)重要的知識(shí)點(diǎn)

一、子序列(不連續(xù))

最長(zhǎng)上升子序列

經(jīng)典問(wèn)題

int lengthOfLIS(int* nums, int numsSize){
    //1.dp[i]表示遍歷到nums[i]時(shí)，最長(zhǎng)遞增子序列的長(zhǎng)度
    //2.遞推式:
    //if(nums[j]<nums[i]) dp[i]=fmax(dp[i],dp[j]+1);
    //3.dp數(shù)組初始化:
    //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;
}

最長(zhǎng)公共子序列

經(jīng)典問(wèn)題

int longestCommonSubsequence(char * text1, char * text2){
    //1.dp[i][j]表示text1[0...i]與text2[0...j]的最長(zhǎng)公共子序列的長(zhǎng)度
    //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數(shù)組初始化:
    //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];
}

不相交的線

該問(wèn)題=求最長(zhǎng)公共子序列（數(shù)組版本）

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];
}

二、子序列(連續(xù))

最長(zhǎng)連續(xù)遞增序列

與最長(zhǎng)上升子序列相比，多了“連續(xù)”這個(gè)條件，故只需要比較相鄰元素大小即可，不相等dp置為1

int findLengthOfLCIS(int* nums, int numsSize){
    //1.dp[i]表示遍歷到nums[i]時(shí)，最長(zhǎng)連續(xù)遞增子序列的長(zhǎng)度
    //2.遞推式:
    //if(nums[i]>nums[i-1]) dp[i]=dp[i-1]+1;
    //3.dp數(shù)組初始化:
    //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;
}

最長(zhǎng)重復(fù)子數(shù)組

與最長(zhǎng)公共子序列相比，多了“連續(xù)”這個(gè)條件，不相等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;
}

最大子序和

很簡(jiǎn)單，i-1到i時(shí)，dp[i]選擇dp[i-1]或者不選擇

int maxSubArray(int* nums, int numsSize){
    //1.dp[i]表示nums[0...i]中最大子數(shù)組和
    //2.遞推式:
    //dp[i]=fmax(dp[i-1]+nums[i],nums[i]);
    //3.dp數(shù)組初始化:
    //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;
}

三、編輯距離

判斷子序列

這題雖然用暴力法設(shè)置兩個(gè)指針遍歷更簡(jiǎn)單，但是為了訓(xùn)練編輯距離題型的思想，建議從動(dòng)態(tài)規(guī)劃入手

bool isSubsequence(char * s, char * t){
    //1.dp[i][j]表示遍歷到s[i]和t[j]時(shí)，兩數(shù)組的最長(zhǎng)公共子序列長(zhǎng)度
    //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數(shù)組初始化:
    //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;
}

兩個(gè)字符串的刪除操作

這一題理解起來(lái)有點(diǎn)吃力，但是好在后面兩題都要用，熟能生巧

int minDistance(char * word1, char * word2){
    //1.dp數(shù)組的含義:
    //dp[i][j]：以i-1為結(jié)尾的字符串word1，和以j-1位結(jié)尾的字符串word2，
    //想要達(dá)到相等，所需要?jiǎng)h除元素的最少次數(shù)
    //2.遞推式:
    //若word1[i-1]==word2[j-1]:
    //      無(wú)需進(jìn)行刪除操作，即刪除次數(shù)無(wú)變化，dp[i][j]=dp[i-1][j-1];
    //若word1[i-1]!=word2[j-1]:
    //      若刪除word1[i-1]，問(wèn)題就變成了dp[i-1][j]基礎(chǔ)上加了一次刪除操作，dp[i][j]=dp[i-1][j]+1;
    //      若刪除word2[j-1]，問(wèn)題就變成了dp[i][j-1]基礎(chǔ)上加了一次刪除操作，dp[i][j]=dp[i][j-1]+1;
    //    綜上，dp[i][j]=fmin(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
    //3.dp數(shù)組初始化:
    //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];
}

不同的子序列

上題是問(wèn)刪除多少次能使得兩字符串相等，這題是問(wèn)有多少種刪除組合能使得兩字符串相等，而且這一題只有s這一個(gè)字符串需要?jiǎng)h除

int numDistinct(char * s, char * t){
    //這題也可以這樣問(wèn):s最多有多少種刪除方法，可以使得s==t
    //1.dp數(shù)組的含義:
    //dp[i][j]：以i-1為結(jié)尾的字符串s，和以j-1位結(jié)尾的字符串t，
    //想要達(dá)到相等，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]開(kāi)始s和t就不匹配了，dp[i][j]=dp[i-1][j];
    //3.dp數(shù)組初始化:
    //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降臨，但其實(shí)只要掌握了第2題，這一題也就多了個(gè)替換操作

int minDistance(char * word1, char * word2){
    //這題是編輯距離問(wèn)題的大BOSS,同時(shí)也是最適合背的,見(jiàn)過(guò)的秒殺，沒(méi)見(jiàn)過(guò)的干瞪眼
    //1.dp[i][j]表示word1的0~i-1部分轉(zhuǎn)換成word2的0~j-1部分所使用的最少操作數(shù)
    //2.遞推式:
    //if(word1[i-1]==word2[j-1])-----------等于,無(wú)需編輯
    //    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]基礎(chǔ)上的操作+1
    //      dp[i][j-1]+1,------------------刪除word2[j-1],就是在word2[0~j-2]與word1[0~i-1]基礎(chǔ)上的操作+1
    //      dp[i-1][j-1]+1-----------------只需要一次替換操作，就能使問(wèn)題變成word1[i-1]==word2[j-1]的情況
    //      );
    //}
    //3.dp數(shù)組初始化:
    //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]的取值依賴(lài)于dp[i+1][j-1]的取值（即外層依賴(lài)于里層）

因此在遍歷順序上也要保證從左下方到右上方，這樣才能保證左下方的數(shù)據(jù)是經(jīng)過(guò)計(jì)算的

int countSubstrings(char * s){
    //1.dp[i][j]表示區(qū)間范圍[i,j]內(nèi)的字符串是否為回文串
    //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數(shù)組初始化:
    //dp[i][j]=false;
    //4.dp數(shù)組遍歷順序
    //dp[i][j]的取值依賴(lài)于dp[i+1][j-1]，則應(yīng)該從下到上、從左到右
    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;
}

最長(zhǎng)回文子串

還是要注意遍歷順序，dp[i][j] 依賴(lài)于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，因此，要保證從左下方到右上方遍歷，這樣才能保證左下方、左方、下方的數(shù)據(jù)是經(jīng)過(guò)計(jì)算的

int longestPalindromeSubseq(char * s){
    //1.dp[i][j]表示字符串在[i,j]范圍內(nèi)的最長(zhǎng)回文子序列長(zhǎng)度
    //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];
}

到此這篇關(guān)于C++中的動(dòng)態(tài)規(guī)劃子序列問(wèn)題分析探討的文章就介紹到這了,更多相關(guān)C++動(dòng)態(tài)規(guī)劃子序列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • opencv3/C++圖像濾波實(shí)現(xiàn)方式

    opencv3/C++圖像濾波實(shí)現(xiàn)方式

    今天小編就為大家分享一篇opencv3/C++圖像濾波實(shí)現(xiàn)方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
    2019-12-12
  • c++類(lèi)型轉(zhuǎn)換及RTTI運(yùn)行階段類(lèi)型識(shí)別

    c++類(lèi)型轉(zhuǎn)換及RTTI運(yùn)行階段類(lèi)型識(shí)別

    這篇文章主要為大家介紹了c++類(lèi)型轉(zhuǎn)換及RTTI運(yùn)行階段類(lèi)型識(shí)別詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步早日升職加薪
    2023-05-05

    • 最新評(píng)論