北龙建设集团有限公司企业网站,青岛路桥建设集团有限公司网站,永久免费微信小程序商城,织梦网站备案1143.最长公共子序列
这题和 718.最长重复子数组 的主要差别在于子序列不要求连续了
这样的话哪怕 nums1[i - 1] 和 nums2[j - 1] 不相等也需要继承之前的最长公共子序列#xff0c;具体继承什么#xff1f;继承的是DP数组矩阵中左上方区域#xff08;包含本行和本列的具体继承什么继承的是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数组定义以nums1[i - 1]和nums2[j - 1]为结尾的两个字符串的最长公共子数组长度// 首行与首列初始化为0vectorvectorint 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矩阵取矩阵包含本行和本列的左上方区域的最大值dp[i][j] std::max(dp[i][j - 1], dp[i - 1][j]);}}}return dp[text1.size()][text2.size()];
} 1035.不相交的线
这题分析一下内在的要求
1、数值得相等才能连线
2、为了不交叉线的起点和终点的次序必须一样
分析一下其实就是最长公共子序列问题所以代码可以直接照搬
int maxUncrossedLines(vectorint nums1, vectorint nums2) {vectorvectorint dp(nums1.size() 1, vectorint(nums2.size() 1, 0));int ans 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;elsedp[i][j] std::max(dp[i][j - 1], dp[i - 1][j]);}}return dp[nums1.size()][nums2.size()];
} 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(vectorint nums) {vectorint dp(nums.size(), 0);dp[0] nums[0];int ans nums[0];for (int i 1; i nums.size(); i) {// dp[i]只能取 nums[i] 或 nums[i] dp[i - 1]dp[i] std::max(nums[i], nums[i] dp[i - 1]);ans std::max(ans, dp[i]);}return ans;
}
