day57|● 1143.最长公共子序列 ● 1035.不相交的线 ● 53. 最大子序和 动态规划

1143. 最长公共子序列

1.代码

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>>f(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]) f[i][j] = f[i - 1][j - 1] + 1;else f[i][j] = max(f[i - 1][j], f[i][j - 1]);}}return f[text1.size()][text2.size()];     }
};

2.递归五部曲

题意：求出两组数据中公共的最大一段数据长度

1.确定dp数组和其下标含义

这里有两个数组，一般需要二维dp

dp[i][j]代表第一个数组下标到达i -1,第二个数组下标到达j -1这两断数据最长公共子序列是多少

也可以理解为第i个元素和第j个元素，这样可以更加方便遍历所有元素，如果不懂自己用另外一种方式试一下

2.确定递推公式

dp[i][j]可以由三个状态得到

一.当两个数组在当前坐标下的元素相同时，就是nums[i - 1]  = nums[j - 1]时f[i -1][j - 1]代表互相上一个元素的最长公共子序列，因为当前相同，所以加1，f[i][lj] = f[i - 1][j - 1] +1

二.当前元素不相等就只能继承以前遍历的全部范围最大值，最大值就是dp[i -1][j]和dp[i][j - 1]

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

三.初始化dp数组

所以全部初始化0就行了

四.确定遍历顺序

两层for循环遍历所有范围，递推出最大范围

五,举例说明dp数组

---

1035. 不相交的线 

1.代码

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>>f(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]) f[i][j] = f[i - 1][j - 1] + 1;else f[i][j] = max(f[i - 1][j], f[i][j - 1]);}}return f[nums1.size()][nums2.size()];   }
};

2.和上一题一样。需要理解

---

53. 最大子数组和

1.代码

class Solution {
public:int maxSubArray(vector<int>& nums) {int len = nums.size();vector<int>f(len, 0);f[0] = nums[0];int result = f[0];for (int i = 1; i < len; i++) {f[i] = max(nums[i], f[i - 1] + nums[i]);result = max(result, f[i]);}return result;}
};

2.动规五部曲（这题必须有1个元素）

题意：给定一个数组求最大连续子序列的和

1,确定dp数组和其下标的含义

由题目和只有一个数组确定，用一维dp数组，dp[i]代表以下标i为下标的范围最大连续子序列的和为多少

2.确定递推公式

dp[i]可以由两种状态得到

一是dp[i - 1] + nums[i]，代表上一个和加上这一个和

二是nums[i]，说明不选前面的，前面的比较小，又因为必须选一个，就选自身

在其中求最大值就是结果

3.初始化

我们必须要有一个元素，f[0] = nums[0]

4.确定遍历顺序

依次遍历全部下标然后求最大值

5.模拟