本文主要是介绍day45.动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1035.不相交的线:
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：
nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。以这种方法绘制线条，并返回可以绘制的最大连线数。
思路:和最长公共子序列是一样的，由图可见1 4 就是两个数组的最长公共子序列。
class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));//确认递推公式int res=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.最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组
是数组中的一个连续部分。
思路:1.贪心法:局部最优推出全局最优，局部最优就是当前两个的和大于0，如果两个和小于0时，将sum重置为0。
class Solution {
public:int maxSubArray(vector<int>& nums) {//1.贪心做法//局部最优推出 全局最优vector<int> res(nums.size()+1);int j=1,i=0;int sum=0;int count=-INT_MAX;for(int i=0;i<nums.size();i++){sum+=nums[i];count=max(sum,count);if(sum<0){sum=0;}}return count;}
};2.动态规划:
思路:定义一个dp数组，这道题目的核心就在于推出递归公式，dp[i]意义在于包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。dp[i]由什么可以推导出来呢，dp[i]取 当前数组的值或者加上当前数组的值 的最大值。定义一个res来取整个数组的最大值。
class Solution {
public:int maxSubArray(vector<int>& nums) {//2.动态规划if(nums.size()==0)return 0;vector<int> dp(nums.size()+1);//dp数组的含义是 dp[i] 代表 0-i 区间的 最大子数组和dp[0]=nums[0];int res=dp[0];//dp[i]=dp[i-1]+nums[i];for(int i=1;i<nums.size();i++){dp[i]=max(nums[i],dp[i-1]+nums[i]);res=max(res,dp[i]);}return res;}
};392.判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
致谢：
特别感谢 @pbrother 添加此问题并且创建所有测试用例。
思路:1.双指针做法，遇到相同的就移动指向字串的指针，当slow等于字串长度时，返回true，否则返回false。
class Solution {
public:bool isSubsequence(string s, string t) {if(s.size()==0){return true;}int slow=0;int fast=0;for(slow,fast;fast<t.size();fast++){if(s[slow]==t[fast]){slow++;if(slow==s.size()){return true;}}}return false;}
};2.动态规划:
思路: 和最长公共子序列也是蛮像的，不过else的语句里只有dp[i][j-1]，没有dp[i-1][j],因为s是子串，不能用子串来判断。 注意 i和j可以等于是，s,size和t.size() 因为 让i可以等于s.size()是为了完整地检查s是否是t的子序列，确保考虑到了s的所有字符与t的不同部分进行匹配的情况。
class Solution {
public:bool isSubsequence(string s, string t) {vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));if (s.empty()) return true;if (t.empty()) return false;for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();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[s.size()][t.size()]==s.size()){return true;}return false;}
};这篇关于day45.动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
