算法|Day46 动态规划14

这篇具有很好参考价值的文章主要介绍了算法|Day46 动态规划14。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LeetCode 1143- 最长公共子序列

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目描述:给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

  • 例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

解题思路

  1. 确定dp数组(dp table)以及下标的含义

dp[i][j],代表字符串1 从0到i-1 字符串2 从0到j-1为止,两个字符的最长公共子序列。

为什么要这样定义呢,方便dp数组的初始化,若dp[i][j]代表从0-i最长公共子序列,那我们dp[0][i]就都得判断,看是否两个对应位置字符相等,来进行初始化。

  1. 确定递推公式

和上一题一样,如果两个对应位字符相等,则使得

  1. dp数组如何初始化

主要就是两大情况: text1[i - 1] 与 text2[j - 1]相同,text1[i - 1] 与 text2[j - 1]不相同

  • 如果text1[i - 1] 与 text2[j - 1]相同,那么找到了一个公共元素,所以dp[i][j] = dp[i - 1][j - 1] + 1;
  • 如果text1[i - 1] 与 text2[j - 1]不相同,那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列,取最大的。

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

  1. 确定遍历顺序

从递归公式其实已经可以看出,一定是从前向后遍历。

  1. 举例推导dp数组
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(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]) {
                    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()];
    }
};

总结:

  • 如果当前俩字符不想等时,取前面字符的最大值,这是和上一题不同的地方。

LeetCode 1035- 不相交的线

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目描述:在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足满足:

  • nums1[i] == nums2[j]
  • 且绘制的直线不与任何其他连线(非水平线)相交。

请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。

以这种方法绘制线条,并返回可以绘制的最大连线数。

解题思路

本题和上一题一模一样,因为我们这题要找不相交的,所以我们找到两个数组的最长公共子序列就一定可以。

1.确定dp数组(dp table)以及下标的含义

dp[i][j],代表字符串1 从0到i-1 字符串2 从0到j-1为止,两个字符的最长公共子序列。

为什么要这样定义呢,方便dp数组的初始化,若dp[i][j]代表从0-i最长公共子序列,那我们dp[0][i]就都得判断,看是否两个对应位置字符相等,来进行初始化。

2.确定递推公式

和上一题一样,如果两个对应位字符相等,则使得

3.dp数组如何初始化

主要就是两大情况: text1[i - 1] 与 text2[j - 1]相同,text1[i - 1] 与 text2[j - 1]不相同

  • 如果text1[i - 1] 与 text2[j - 1]相同,那么找到了一个公共元素,所以dp[i][j] = dp[i - 1][j - 1] + 1;
  • 如果text1[i - 1] 与 text2[j - 1]不相同,那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列,取最大的。

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

4.确定遍历顺序

从递归公式其实已经可以看出,一定是从前向后遍历。

5.举例推导dp数组

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int s1 = nums1.size();
        int s2 = nums2.size();
        vector<vector<int>> dp(s1+1,vector<int>(s2+1,0));
        for(int i=1;i<=s1;i++){
            for(int j=1;j<=s2;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[s1][s2];
    }
};

总结:

  • 和上一题一样的

LeetCode 53- 最大子数组和

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目描述:给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

解题思路

  1. 确定dp数组(dp table)以及下标的含义

dp[i]:以i为结尾的连续子数组的最大的和。

  1. 确定递推公式

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

  • dp[i - 1] + nums[i],即:nums[i]加入当前连续子序列和
  • nums[i],即:从头开始计算当前连续子序列和
  1. dp数组如何初始化

全部初始化为0

  1. 确定遍历顺序

顺序遍历

  1. 举例推导dp数组
class Solution {
public://没AC是因为开始把res设置为了int的最小值,应该设置为nums[0]的
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(),0);
        int res = nums[0];
        if(nums.size() == 1) return nums[0];
        dp[0] = nums[0];
        for(int i=1;i<nums.size();i++){
            dp[i] = max(dp[i-1]+nums[i],nums[i]); 
            res = max(res,dp[i]);
        }
        return res;
    }
};

总结:文章来源地址https://www.toymoban.com/news/detail-677781.html

  • 本题开始一直错,是初始化res错了,一直初始化成int最小值,那么如果就两个数的时候,它就会取第二个数。因为我们i是从1开始的,所以一直错。

到了这里,关于算法|Day46 动态规划14的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 研习代码 day46 | 动态规划——子序列问题2

            1.1 题目         给定两个字符串  text1  和  text2 ,返回这两个字符串的最长  公共子序列  的长度。如果不存在  公共子序列  ,返回  0  。         一个字符串的  子序列   是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下

    2024年02月04日
    浏览(35)
  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(46)
  • 算法训练day41|动态规划 part03(LeetCode343. 整数拆分、96.不同的二叉搜索树)

    题目链接🔥🔥 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 说明: 你可以假设 n 不小于 2 且不大于

    2024年02月10日
    浏览(39)
  • 算法打卡day39|动态规划篇07| Leetcode 70. 爬楼梯(进阶版)、322. 零钱兑换、279.完全平方数

    Leetcode 70. 爬楼梯(进阶版) 题目: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,

    2024年04月14日
    浏览(65)
  • 动态规划Day14(子序列第二天)

    目录 1143.最长公共子序列 看到题目的第一想法                看到代码随想录之后的想法 自己实现过程中遇到的困难 1035.不相交的线 看到题目的第一想法                看到代码随想录之后的想法 自己实现过程中遇到的困难 53. 最大子序和 看到题目的第一想法     

    2024年01月24日
    浏览(37)
  • 剑指offer(C++)-JZ46:把数字翻译成字符串(算法-动态规划)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 有一种将字母编码成数字的方式:\\\'a\\\'-1, \\\'b-2\\\', ... , \\\'z-26\\\'。 现在给一串数字,返回有多少种可能的译码结果 数据范围:字符串长度满足 0n≤90 进阶:空间复杂度

    2024年02月07日
    浏览(44)
  • 算法笔记14.动态规划

    就是切割问题变成一堆小问题,最好子问题之间可以递推,这样就能利用之前的子问题的答案得出新的结果。 可以削减总量,比如求n个数的什么什么,可以削n的大小,n削到n-1……一直到1,1的结果很好求,然后利用1的结果求2,然后再一直求到n。 也可以不削总量削单量,比

    2024年04月15日
    浏览(26)
  • Leetcoder Day39| 动态规划part06 完全背包问题

    有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 每件物品都有无限个(也就是可以放入背包多次) ,求解将哪些物品装入背包里物品价值总和最大。 示例: 背包最大重量为4。 物品为: 重量 价值 物品0 1 15 物品1 3 20 物品2 4 30 每

    2024年03月25日
    浏览(38)
  • 算法记录 | Day55 动态规划

    思路: 1.确定dp数组(dp table)以及下标的含义: dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为 dp[i][j] 。 2.确定递推公式: if (s[i - 1] == t[j - 1]) t中找到了一个字符在s中也出现了, dp[i][j] = dp[i - 1][j - 1] + 1 if (s[i - 1] != t[j - 1]) 相当于t要

    2024年02月03日
    浏览(47)
  • 算法|Day40 动态规划9

    LeetCode 198- 打家劫舍 题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 题目描述 :你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上

    2024年02月12日
    浏览(29)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包