1143.?最長公共子序列
思路：
dp[i][j]：以0~i-1和0~j-1位置中最長公共子序列的長度為dp[i][j]酗昼。遞推關(guān)系：如果nums1[i-1]與nums2[i-1]相等的話廊谓，dp[i][j]=dp[i-1][j-1]+1,如果二者不相等，可能是nums1[i-1]==nums2[j-2],也可能是nums1[i-2]==nums2[j-1]麻削，所以dp[i][j]=max(dp[i][j-1],dp[i-1][j])蒸痹。初始化：由dp[i][j]的定義可以知道dp[i][0]、dp[0][j]都應(yīng)該初始化為0。遍歷順序：從小到大，從前向后任岸。
代碼：
class Solution {
public:
? ? int longestCommonSubsequence(string text1, string text2) {
? ? ? ? vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
? ? ? ? for(int i=1;i<=text1.size();i++)
? ? ? ? {
? ? ? ? ? ? for(int j=1;j<=text2.size();j++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(text1[i-1]==text2[j-1])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? dp[i][j]=dp[i-1][j-1]+1;
? ? ? ? ? ? ? ? }else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return dp[text1.size()][text2.size()];
? ? }
};
1035.?不相交的線
思路：
本題思路和上一題是一樣的，本題的難點在于如何保證線與線之間不能相交蝙叛，也就是當(dāng)前的元素只能與之前的元素連線而不能與之后的元素連線，這就是上面一道題的解法公给。
代碼：
class Solution {
public:
? ? int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
? ? ? ? vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
? ? ? ? for(int i=1;i<=nums1.size();i++)
? ? ? ? {
? ? ? ? ? ? for(int j=1;j<=nums2.size();j++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(nums1[i-1]==nums2[j-1])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? dp[i][j]=dp[i-1][j-1]+1;
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return dp[nums1.size()][nums2.size()];
? ? }
};
53.?最大子數(shù)組和
思路：
dp[i]:下標(biāo)為i的最大子數(shù)組的和為dp[i]（包含第i位元素）借帘。遞推關(guān)系：如果該位置的元素大于0，則為dp[i-1]+nums[i]淌铐，如果該位的元素小于0肺然，則應(yīng)該不加上這一位，但是子數(shù)組要保持?jǐn)?shù)組的連續(xù)性腿准，所以這里應(yīng)該從頭開始际起，所以dp[i]=max(dp[i-1]+nums[i],nums[i])拾碌。初始化：dp[0]=nums[0]。遍歷關(guān)系：從小到大街望。
代碼：
class Solution {
public:
? ? int maxSubArray(vector<int>& nums) {
? ? ? ? int len=nums.size();
? ? ? ? if(len==0)return 0;
? ? ? ? vector<int> dp(len,0);
? ? ? ? dp[0]=nums[0];
? ? ? ? int res=dp[0];
? ? ? ? for(int i=1;i<len;i++)
? ? ? ? {
? ? ? ? ? ? dp[i]=max(dp[i-1]+nums[i],nums[i]);
? ? ? ? ? ? if(res<dp[i])? res=dp[i];
? ? ? ? }
? ? ? ? return res;
? ? }
};
