leetcode-300-最長遞增子序列

dp[i]表示i之前包括i的以nums[i]結尾的最長遞增子序列的長度

dp[j]是(0,i-1)不包括i的以nums[i-1]結尾的最長遞增子序列長度

int lengthOfLIS(int* nums, int numsSize) {if(numsSize <= 1)return numsSize;int dp[numsSize];for(int i = 0 ; i < numsSize ; i++){dp[i] = 1;}int res = 1;for(int i = 1 ; i < numsSize ; i++){for(int j = 0 ; j < i ; j++){if(nums[i] > nums[j])dp[i] = fmax(dp[i],dp[j]+1);}res = fmax(res,dp[i]);}return res;
}

leetcode-674-最長連續遞增序列

不連續遞增子序列的跟前0-i 個狀態有關，連續遞增的子序列只跟前一個狀態有關

int findLengthOfLCIS(int* nums, int numsSize) {if(numsSize <= 1)return numsSize;int dp[numsSize];for(int i = 0 ; i < numsSize ; i++)dp[i] = 1;int res = 0;for(int i = 1 ; i < numsSize ; i++){if(nums[i] > nums[i-1])dp[i] = dp[i-1]+1;res = fmax(res,dp[i]);}return res;
}

leetcode-718-最長重復子數組

dp[i][j] ：以下標i - 1為結尾的A，和以下標j - 1為結尾的B，最長重復子數組長度為dp[i][j]。

int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size) {int dp[nums1Size+1][nums2Size+1];for(int i = 0 ; i <= nums1Size ; i++){memset(dp[i],0,sizeof(int)*(nums2Size+1));}int res = 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;}res = fmax(res,dp[i][j]);}}return res;
}

leetcode-1143-最長公共子序列

區別于 349.兩個數組交集?

int longestCommonSubsequence(char* text1, char* text2) {int len1 = strlen(text1);int len2 = strlen(text2);int dp[len1+1][len2+1];for(int i = 0 ; i <= len1 ; i++){memset(dp[i],0,sizeof(int)*(len2+1));}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];
}

leetcode-1035-不相交的線

本質是求最長公共子序列

int maxUncrossedLines(int* nums1, int nums1Size, int* nums2, int nums2Size) {int dp[nums1Size+1][nums2Size+1];for(int i = 0 ; i <= nums1Size ; i++){memset(dp[i],0,sizeof(int)*(nums2Size+1));}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];
}