溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
今天小編給大家分享一下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++中的動態規劃子序列問題怎么解決”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
