首页 > 其他分享 >刷题笔记53 动态规划14

刷题笔记53 动态规划14

时间:2023-05-29 22:35:30浏览次数:47  
标签:size 14 nums int 53 vector 动态 dp 刷题

@

目录

动态规划

● 1143.最长公共子序列
● 1035.不相交的线
● 53. 最大子序和 动态规划

1143.最长公共子序列

1143.最长公共子序列

法1:动态规划

   int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>>dp(text1.size() + 1, vector<int>(text2.size() + 1,0));
        int ans = 0;
        for (int i = 1; i <= text1.size(); ++i) {
            for (int j = 1; j <= text2.size(); ++j) {
                if (text1[i - 1] == text2[j - 1]) {//此处为何比较的是(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[text1.size()][text2.size()];
    }

1035.不相交的线

1035.不相交的线
法1:动态规划

       int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>>dp(nums1.size() + 1,vector<int>(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()];
    }

53. 最大子序和 动态规划

53. 最大子序和 动态规划

法1:动态规划

  int maxSubArray(vector<int>& nums) {
        //动态规划
        vector<int>dp(nums.size(),0);

        dp[0] = nums[0];
        int ans = dp[0];//INT_MIN
        for (int i = 1; i < nums.size(); ++i) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            if (ans < dp[i]) ans = dp[i];
        }
        return ans;
    }

标签:size,14,nums,int,53,vector,动态,dp,刷题
From: https://www.cnblogs.com/asupersource-tech/p/17441866.html

相关文章

  • poj 1451(Trie)
    题意:就是让你模拟手机输入单词。具体就是给你一些单词,以及该单词被使用的频数,这个频数也是该单词前缀的使用频数,当然不同的单词有可能有相同的前缀,那么这个相同的前缀的使用频数就是这两个单词使用频数之和,以此类推。然后再给你一些数字串,让你针对该数字串的每一个前缀输出它的最有......
  • 刷题笔记52 动态规划 part13
    @目录动态规划300.最长递增子序列674.最长连续递增序列718.最长重复子数组动态规划●300.最长递增子序列●674.最长连续递增序列●718.最长重复子数组300.最长递增子序列300.最长递增子序列法1:动态规划intlengthOfLIS(vector<int>&nums){//未考虑......
  • hdu 1534(差分约束)
    题意:安排计划,有4种约束方式,给出你这些时间的n个约束..如果计划是可行的,求出每一件事发生的最早时间..否则输出“impossible”..①.FAFaba要在b完成后完成..②.FASaba要在b开始前完成..③.SASaba要在b开始前开始..④.SAFaba要在b结束前开......
  • hdu 1532(最大流)
    解题思路:这是一道典型的模板题,直接套用EK算法即可。。。我感觉最大流的本质就是能否找到一个从源点到汇点的增广路径,并将其最小的边作为增加值,沿着增广路上的边进行更新。AC:#include<iostream>#include<cstdio>#include<cstring>#include<queue>usingnamespacestd;consti......
  • [刷题笔记55 动态规划15]
    @目录动态规划392.判断子序列115.不同的子序列动态规划●392.判断子序列●115.不同的子序列392.判断子序列392.判断子序列法1:动态规划boolisSubsequence(strings,stringt){//动态规划vector<vector<int>>dp(s.size()+1,vector<int>(t.size(......
  • 「解题报告」[ARC114E] Paper Cutting 2
    Kaguya随机点了一道题,结果还挺educational,写一下。不过好像挺套路的。首先第一件事,发现从现有的线段里选一个隔开这个东西太丑了。我们考虑转化一下题意。我们仍然在原矩形上划线,但是划完线后并不割开,而是一直在原矩形上操作。可以发现,这个操作是和原来的操作是等价的,因为我们......
  • ceph14安装部署(老版本)
    1.基础环境配置IP主机名10.0.0.10storage0110.0.0.11storage0210.0.0.12storage031.1关闭防火墙与selinux所有节点sed-i"s/SELINUX=enforcing/SELINUX=disabled/g"/etc/selinux/config;setenforce0;systemctlstopfirewalld;systemctldisable......
  • LeetCode 530. 二叉搜索树的最小绝对差
    题目链接:LeetCode530.二叉搜索树的最小绝对差题意:给你一个二叉搜索树的根节点root,返回树中任意两不同节点值之间的最小差值。差值是一个正数,其数值等于两值之差的绝对值。解题思路:递归法1既然是二叉搜索树,那么中序遍历一定是有序的,因此最小的插值一定出现在相邻的两个......
  • hdu 5367(线段树+区间合并)
    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5367官方题解:对于求“高山脉”长度,可以利用线段树。树节点中保存左高度连续长度,左高度连续区间的高度,左高度连续区间的状态(即是否高于第一个高度不同的山),右高度连续长度,右高度连续区间的高度,右高度连续区间的状态,每段区间内的“......
  • sockjs.js:1603 GET http://localhost/sockjs-node/info?t=1685340190468 net::ER
    vue项目报错不影响运行,但控制台看到这报错,属实不舒服 解决方法:进入\node_modules\sockjs-client\dist\sockjs.js注释1603行   刷新页面,没报错了 ......