代码随想录算法训练营 ---第五十二天

news/2024/11/23 2:37:38/

第一题:

简介:

动态规划五部曲:

1.确定 dp数组下标的定义

   dp[i]  到达 i 时 最长递增子序列的长度

2.确定递推公式

     我们确定当前的最大长度需要遍历前面所有的最大长度,然后如果序列最后一个值小于nums[i]那就dp[j] + 1;然后不断遍历保持最大。

      if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

3.初始化dp数组

    vector<int> dp(nums.size(), 1);

  因为一个数也是一个递增序列

4.确定遍历顺序

 for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}if (dp[i] > result) result = dp[i]; // 取长的子序列}

5.打印数组

代码实现:

  int lengthOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);int result = 0;for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}if (dp[i] > result) result = dp[i]; // 取长的子序列}return result;}

第二题:

简介:

大家可以看一看第一题与第二题大的不同之处。第二题新增了一个条件:必须是连续的。所以,我们不需要去遍历数组去得到从前最大的子串长度。因为是连续的所以我们只需要知道前一个数是否小于当前数。所以递推公式为:

其他与第一题相同。

代码实现: 

   int findLengthOfLCIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);int result =0;for(int i = 1; i < nums.size(); i++){if(nums[i]>nums[i-1])dp[i] = dp[i-1]+1;if(dp[i]>result)result =dp[i];}return result;}

第三题:

简介:

本题先看实例图:

一个二维数组dp[i][j]进行循环遍历,如果遇到相等值就让左上角的值加一赋给当前值,但是为什么要左上角加一赋值,因为我们可以在脑中想想如果两个完全相同的数组组成二维数组,把列和行值相同的交接处值为1,其他为零。把1连接起来是不是一条从左上到右下的对角线所以:最长重复子数组它的值dp[i][j]是由dp[i-1][j-1]计算而出的所以递推公式为:

  if(nums1[i-1]==nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1;

 如果两值相等就让dp[i-1][j-1]加一。

动态规划五部曲:

1.确定 dp数组下标的定义

 dp[i][j] :以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。

2.确定递推公式

     if(nums1[i-1]==nums2[j-1]) dp[i][j] = dp[i - 1][j - 1] + 1;;

3.初始化dp数组

    都初始化为零。

4.确定遍历顺序

 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;if(dp[i][j]>result) result =dp[i][j];}}

5.打印数组

代码实现: 

    int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));dp[0][0] =0;int result;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;if(dp[i][j]>result) result =dp[i][j];}}return result;}

总结:

今天的题较有规律的题,要总结一下。继续加油!

 


http://www.ppmy.cn/news/1255144.html

相关文章

Task中Wait()和Result造成死锁

在使用Task的时候&#xff0c;一不留神就会造成死锁&#xff0c;而且难以发现&#xff0c;尤其是业务繁多的情况下&#xff0c;一个Task嵌套另一个Task的时候&#xff0c;下面就演示一下&#xff0c;在什么情况下&#xff0c;会产生Wait()和Result的死锁&#xff0c;因此&#…

Chat-GPT原理

GPT原理 核心是基于Transformer 架构 英文原文&#xff1a; ​ Transformers are based on the “attention mechanism,” which allows the model to pay more attention to some inputs than others, regardless of where they show up in the input sequence. For exampl…

掌握视频剪辑技巧,轻松自定义视频速率,打造个性化出彩视频

你是否曾经因为视频节奏平淡而缺乏吸引力而苦恼&#xff1f;现在&#xff0c;我们为你推荐一款视频批量剪辑工具&#xff0c;让你轻松自定义视频速率&#xff0c;实现出彩个性化视频。 首先第一步&#xff0c;我们要打开好简单批量智剪&#xff0c;并登录账号。 第二步&#x…

外包干了2年,技术退步明显。。。

前言 简单的说下&#xff0c;我大学的一个同学&#xff0c;毕业后我自己去了自研的公司&#xff0c;他去了外包&#xff0c;快两年了我薪资、技术各个方面都有了很大的提升&#xff0c;他在外包干的这两年人都要废了&#xff0c;技术没一点提升&#xff0c;学不到任何东西&…

【计算机网络笔记】802.11无线局域网

系列文章目录 什么是计算机网络&#xff1f; 什么是网络协议&#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能&#xff08;1&#xff09;——速率、带宽、延迟 计算机网络性能&#xff08;2&#xff09;…

[ffmpeg] find 编码器

背景 整理 ffmpeg 中&#xff0c;如何通过名字或者 id 找到对应编码器的。 具体流程 搜索函数 avcodec_find_encoder // 通过 ID 搜索编码器 avcodec_find_encoder_by_name // 通过名字搜索编码器源码分析 ffmpeg 中所有支持的编码器都会注册到 codec_list.c 文件中&…

C语言结构体详解(二)(能看懂文字就能明白系列)文章很长,慢慢品尝

系列文章目录 第一章 结构体的介绍和基本使用 &#x1f31f; 个人主页&#xff1a;古德猫宁- &#x1f308; 信念如阳光&#xff0c;照亮前行的每一步 文章目录 系列文章目录&#x1f308; *信念如阳光&#xff0c;照亮前行的每一步* 前言前面一篇文章主要介绍了结构体的基础…

SCAU:字母分类统计

字母分类统计 Time Limit:1000MS Memory Limit:65535K 题型: 编程题 语言: G;GCC;VC 描述 输入一行以换行符结束的字符&#xff0c;统计并输出其中英文字母、数字、空格和其它字符的个数。输入格式 一行字符&#xff0c;以换行符结束输出格式 一行4个数字分别为&#…