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è)入門，好讓讀者掌握這個(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]開始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í)也是最適合背的,見過(guò)的秒殺，沒(méi)見過(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]的取值依賴于dp[i+1][j-1]的取值（即外層依賴于里層）
因此在遍歷順序上也要保證從左下方到右上方，這樣才能保證左下方的數(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]的取值依賴于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] 依賴于 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)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- C++動(dòng)態(tài)規(guī)劃計(jì)算最大子數(shù)組
- C++動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)矩陣鏈乘法
- C++動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)查找最長(zhǎng)公共子序列
- C++?動(dòng)態(tài)規(guī)劃算法使用分析
- C++編輯距離（動(dòng)態(tài)規(guī)劃）
- c++動(dòng)態(tài)規(guī)劃經(jīng)典算法
- C++動(dòng)態(tài)規(guī)劃之最長(zhǎng)公子序列實(shí)例
- C++動(dòng)態(tài)規(guī)劃之背包問(wèn)題解決方法
- C++動(dòng)態(tài)規(guī)劃中關(guān)于背包問(wèn)題講解
相關(guān)文章
C++ LeetCode1775通過(guò)最少操作次數(shù)使數(shù)組和相等
這篇文章主要為大家介紹了C++ LeetCode1775通過(guò)最少操作次數(shù)使數(shù)組和相等，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-12-12
C/C++實(shí)現(xiàn)貪吃蛇逐步運(yùn)動(dòng)效果
這篇文章主要為大家詳細(xì)介紹了C/C++實(shí)現(xiàn)貪吃蛇逐步運(yùn)動(dòng)效果的相關(guān)資料，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2016-05-05
本文主要介紹了C語(yǔ)言宏定義#define的使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-01-01
this 指針在C++類和對(duì)象中是個(gè)很方便實(shí)用的關(guān)鍵字，可以簡(jiǎn)化對(duì)象成員屬性的調(diào)用，使代碼表達(dá)的含義更加準(zhǔn)確；在之前的學(xué)習(xí)中我們都可以判斷變量所占內(nèi)存空間大小，那么我們創(chuàng)建的類對(duì)象所占的內(nèi)存空間怎么計(jì)算呢?想知道this的妙用和類對(duì)象占用的內(nèi)存空間就來(lái)跟我學(xué)習(xí)吧2022-06-06
這篇文章介紹了C++超集C++/CLI模塊的基本用法，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07
淺談c++調(diào)用python鏈接的問(wèn)題及解決方法
下面小編就為大家?guī)?lái)一篇淺談c++調(diào)用python鏈接的問(wèn)題及解決方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-03-03
Windows安裝Qt6.4.2及簡(jiǎn)單驗(yàn)證
本文主要介紹了Windows安裝Qt6.4.2及簡(jiǎn)單驗(yàn)證，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02
深入Windows下的回車是回車換行(\r\n)還是換行回車(\n\r)的詳解
本篇文章對(duì)Windows下的回車是回車換行(\r\n)還是換行回車(\n\r)進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
俄羅斯方塊是一個(gè)最初由阿列克謝帕吉特諾夫在蘇聯(lián)設(shè)計(jì)和編程的益智類視頻游戲。本文將利用Matlab實(shí)現(xiàn)這一經(jīng)典的小游戲，需要的可以參考一下2022-03-03
深入分析父子線程、進(jìn)程終止順序不同產(chǎn)生的結(jié)果
本篇文章是對(duì)父子線程、進(jìn)程終止順序不同產(chǎn)生的結(jié)果進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05