1143.最长公共子序列
这题和 718.最长重复子数组 的主要差别在于子序列不要求连续了
这样的话哪怕 nums1[i – 1] 和 nums2[j – 1] 不相等也需要继承之前的最长公共子序列，具体继承什么？继承的是DP数组矩阵中左上方区域（包含本行和本列的）的最大值
和 718 相比主要差别在于递推公式：
1、DP数组定义：两个维度表示两个数组的索引，dp[i][j]表示以nums1[i – 1]和nums2[j – 1]为结尾的两个字符串的最长公共子序列长度
2、DP数组初始化：首行与首列元素无意义，但为了递推公式将其初始化为0，其余元素随意
3、递推公式：
如果nums1[i – 1] == nums2[j – 1]，那么dp[i][j] = dp[i – 1][j -1] + 1（同718）
如果nums1[i – 1] != nums2[j – 1]，dp[i][j] 取dp[i][j – 1] 和 dp[i – 1][j] 中的较大值
（左上方矩阵到达dp[i][j]的唯二途径就是dp[i][j – 1] 和 dp[i – 1][j] ，所以通过不断递推，这两个值可以获取左上方矩阵的最大值）
4、遍历顺序：从上到下从左到右遍历，先遍历nums1或nums2都可以
int longestCommonSubsequence(string text1, string text2) {
// DP数组定义：以nums服务器托管网1[i - 1]和nums2[j - 1]为结尾的两个字符串的最长公共子数组长度
// 首行与首列初始化为0
vector> dp(text1.size() + 1, vector(text2.size() + 1, 0));
for (int i = 1; i 1035.不相交的线
这题分析一下内在的要求：
1、数值得相等才能连线
2、为了不交叉，线的起点和终点的次序必须一样
分析一下其实就是最长公共子序列问题，所以代码可以直接照搬：
int maxUncrossedLines(vector& nums1, vector& nums2) {
vector> dp(nums1.size() + 1, vector(nums2.size() + 1, 0));
int ans = 0;
for (int i = 1; i 53.最大子数组和
这题对比一下贪心解法就能发现dp的无脑之处了
贪心解法需要分析什么情况下可以累加，什么时候需要删去
动规解法只要分析好状态以及状态的转移，之后的具体判断全部交给递推过程就可以了
1、DP数组定义：dp[i]以nums[i]为最后一个元素的最大子数组和
2、DP数组初始化：dp[0] = nums[0]，第一个元素的值作为初始状态
3、递推公式：dp[i] 的取值只有两种情况：
1、之前的值加上nums[i]：dp[i] = nums[i服务器托管网] + dp[i – 1]
2、之前的值删去，从nums[i]重新开始：dp[i] =nums[i]
dp[i] 取以上两种情况的较大值即可，不用考虑什么情况下选1什么情况下选2：
dp[i] = max(nums[i], nums[i] + dp[i – 1])
4、遍历顺序：从左到右遍历
int maxSubArray(vector& nums) {
vector dp(nums.size(), 0);
dp[0] = nums[0];
int ans = nums[0];
for (int i = 1; i 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
