C++中的動態(tài)規(guī)劃子序列問題分析探討
更新時間：2023年03月15日 08:55:05 作者：清風何渡
可能有些讀者有接觸過動態(tài)規(guī)劃，可能也有一些讀者以前完全不知道動態(tài)規(guī)劃這個東西，別擔心，我這篇文章會為讀者做一個入門，好讓讀者掌握這個重要的知識點
一、子序列(不連續(xù))
最長上升子序列
經(jīng)典問題
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數(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;
}最長公共子序列
經(jīng)典問題
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數(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];
}不相交的線
該問題=求最長公共子序列（數(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ù))
最長連續(xù)遞增序列
與最長上升子序列相比，多了“連續(xù)”這個條件，故只需要比較相鄰元素大小即可，不相等dp置為1
int findLengthOfLCIS(int* nums, int numsSize){
//1.dp[i]表示遍歷到nums[i]時，最長連續(xù)遞增子序列的長度
//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;
}最長重復子數(shù)組
與最長公共子序列相比，多了“連續(xù)”這個條件，不相等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]中最大子數(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è)置兩個指針遍歷更簡單，但是為了訓練編輯距離題型的思想，建議從動態(tài)規(guī)劃入手
bool isSubsequence(char * s, char * t){
//1.dp[i][j]表示遍歷到s[i]和t[j]時，兩數(shù)組的最長公共子序列長度
//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;
}兩個字符串的刪除操作
這一題理解起來有點吃力，但是好在后面兩題都要用，熟能生巧
int minDistance(char * word1, char * word2){
//1.dp數(shù)組的含義:
//dp[i][j]：以i-1為結(jié)尾的字符串word1，和以j-1位結(jié)尾的字符串word2，
//想要達到相等，所需要刪除元素的最少次數(shù)
//2.遞推式:
//若word1[i-1]==word2[j-1]:
// 無需進行刪除操作，即刪除次數(shù)無變化，dp[i][j]=dp[i-1][j-1];
//若word1[i-1]!=word2[j-1]:
// 若刪除word1[i-1]，問題就變成了dp[i-1][j]基礎(chǔ)上加了一次刪除操作，dp[i][j]=dp[i-1][j]+1;
// 若刪除word2[j-1]，問題就變成了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];
}不同的子序列
上題是問刪除多少次能使得兩字符串相等，這題是問有多少種刪除組合能使得兩字符串相等，而且這一題只有s這一個字符串需要刪除
int numDistinct(char * s, char * t){
//這題也可以這樣問:s最多有多少種刪除方法，可以使得s==t
//1.dp數(shù)組的含義:
//dp[i][j]：以i-1為結(jié)尾的字符串s，和以j-1位結(jié)尾的字符串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數(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降臨，但其實只要掌握了第2題，這一題也就多了個替換操作
int minDistance(char * word1, char * word2){
//這題是編輯距離問題的大BOSS,同時也是最適合背的,見過的秒殺，沒見過的干瞪眼
//1.dp[i][j]表示word1的0~i-1部分轉(zhuǎn)換成word2的0~j-1部分所使用的最少操作數(shù)
//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]基礎(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-----------------只需要一次替換操作，就能使問題變成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)過計算的
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;
}最長回文子串
還是要注意遍歷順序，dp[i][j] 依賴于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，因此，要保證從左下方到右上方遍歷，這樣才能保證左下方、左方、下方的數(shù)據(jù)是經(jīng)過計算的
int longestPalindromeSubseq(char * s){
//1.dp[i][j]表示字符串在[i,j]范圍內(nèi)的最長回文子序列長度
//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++中的動態(tài)規(guī)劃子序列問題分析探討的文章就介紹到這了,更多相關(guān)C++動態(tài)規(guī)劃子序列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
EasyX是針對C/C++的圖形庫，可以幫助使用C/C++語言的程序員快速上手圖形和游戲編程。本文將為大家詳細講講EasyX的鼠標操作，需要的可以參考一下2022-07-07
這篇文章主要介紹了C++ STL之slist單向鏈表容器使用方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-04-04
通過點擊程序界面上不同的布局按鈕,使主工作區(qū)呈現(xiàn)出不同的頁面布局,多個布局之間可以通過點擊不同布局按鈕切換,支持的最多的窗口為9個,不同布局下窗口數(shù)隨之變化,這篇文章主要介紹了Qt實現(xiàn)手動切換多種布局的完美方案,需要的朋友可以參考下2024-07-07
這篇文章主要為大家詳細介紹了基于QT實現(xiàn)文件上傳和下載功能，支持斷點續(xù)傳，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
Qt圖形圖像開發(fā)之高性能曲線圖模塊QCustomplot庫詳細使用方法與實例(支持動、靜曲線圖)
這篇文章主要介紹了Qt圖形圖像開發(fā)之高性能曲線圖模塊QCustomplot庫詳細使用方法與實例(支持動、靜曲線圖),需要的朋友可以參考下2020-03-03
隱式類型轉(zhuǎn)換是安全的,顯式類型轉(zhuǎn)換是有風險的,C語言之所以增加強制類型轉(zhuǎn)換的語法,就是為了強調(diào)風險,讓程序員意識到自己在做什么,本文將給大家詳細介紹一下C++中的四種類型轉(zhuǎn)換運算符,需要的朋友可以參考下2023-09-09
C/C++ Qt 數(shù)據(jù)庫與Chart歷史數(shù)據(jù)展示
這篇文章主要介紹了Qt利用Qchart組件展示數(shù)據(jù)庫中的歷史數(shù)據(jù)。文中的示例代碼講解清晰，具有一定的學習和工作價值，感興趣的小伙伴可以學習一下2021-12-12
今天小編就為大家分享一篇opencv3/C++圖像濾波實現(xiàn)方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2019-12-12 
這篇文章主要為大家介紹了c++類型轉(zhuǎn)換及RTTI運行階段類型識別詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步早日升職加薪
2023-05-05