山东省建设执业师网站,建设网站图片,企业网站建设费是无形资产吗,国外外贸网站大全最长公共子序列 dp[i][j] 表示字符串1中 [0, i-1] 子串与字符串2中 [0, j-1] 子串之间的最长公共子序列长度。注意这里并不要求公共子序列一定以下标 i-1 或 j-1 结尾。因为这里的公共子序列不必须连续#xff0c;这样定义可以使得递推方便一些。 当进行遍历递推时#xff0c…最长公共子序列 dp[i][j] 表示字符串1中 [0, i-1] 子串与字符串2中 [0, j-1] 子串之间的最长公共子序列长度。注意这里并不要求公共子序列一定以下标 i-1 或 j-1 结尾。因为这里的公共子序列不必须连续这样定义可以使得递推方便一些。 当进行遍历递推时无非有text1[i-1] text2[j-1]和text1 ! text2[j-1]两种情况。如果相等自然dp[i][j] dp[i - 1][j - 1] 1如果不相等则应该从 dp[i-1][j] 和 dp[i][j-1] 中挑更大的那一个因为不要求公共序列连续 初始化借鉴了昨天的题目在dp数组定义上绕了一下方便了第一行和第一列的初始化。
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vectorvectorint dp(text1.size() 1, vectorint(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 - 1][j], dp[i][j - 1]);}}}return dp[text1.size()][text2.size()];}
};不相交的线 直线不能相交这就是说明在序列1中找到一个与序列2相同的子序列且这个子序列不能改变相对顺序只要相对顺序不改变链接相同数字的直线就不会相交。直线的数目等于两个序列之间的最长公共子序列长度。
class Solution {
public:int maxUncrossedLines(vectorint nums1, vectorint nums2) {vectorvectorint dp(nums1.size() 1, vectorint(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()];}
};最大子序和 这道题之前已经通过贪心算法解决过一次了局部上保证每一次累加得到的都是正值如果遇到负值则将累加和置0重新开始累加因为负值只会使总和变小。
class Solution {
public:int maxSubArray(vectorint nums) {int count 0;int result INT_MIN;for(int i 0; i nums.size(); i) {count nums[i];if(count result) {result count;}if(count 0) {count 0;}}return result;}
};动态规划法
dp[i] 表示以 nums[i] 结尾的所有连续子数组的最大和。 在递推时只需要考虑要不要继续累加还是重新开始加。dp[i] max(dp[i - 1] nums[i], nums[i])。 初始化dp[0]其最大和只能为nums[0]dp[0] nums[0]。 由于每次计算的都是必须以该下标结尾的子数组的最大和所以最终结果要取dp数组中的最大值考虑每个位置结尾的子数组。
class Solution {
public:int maxSubArray(vectorint nums) {// dp[i]表示以nums[i]结尾的所有子数组和的最大值vectorint dp(nums.size(), 0);dp[0] nums[0];int result dp[0]; // 注意这里初始化为dp[0]不然就把dp[0]落下了for(int i 1; i nums.size(); i) {dp[i] max(dp[i - 1] nums[i], nums[i]);if(dp[i] result) {result dp[i];}}return result;}
};
