leetcode:3176 求出最长好子序列 使用动态规划

2024-09-07 05:52

本文主要是介绍leetcode:3176 求出最长好子序列 使用动态规划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

3176. 求出最长好子序列

题目链接https://leetcode.cn/problems/find-the-maximum-length-of-a-good-subsequence-i/

题目描述

给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标 i 满足 seq[i] != seq[i + 1] ,那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。

实例1:

输入:nums = [1,2,1,1,3], k = 2
输出:2
解释:最长的好子序列是 [1,2,1,1] 。

实例2:

输入:nums = [1,2,3,4,5,1], k = 0
输出:2
解释:最长好子序列为 [1,1] 。

题目解析

根据题目可知,我们需要找到一个整数序列,满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标 i 满足 seq[i] != seq[i + 1] 。

我们可以考虑使用动态规划来解决这个问题。

定义dp[i][j]表示以nums[i]结尾,最多有j个下标i 满足seq[i] != seq[i + 1]的子序列的长度。其中,0<=j<=k。

我们可以初始化dp[i][0]=1,表示以nums[i]结尾的,最多有0个下标i满足seq[i] != seq[i + 1]的子序列的长度为1。

那么,我们可以知道,当前dp[i][j]的值,和dp[cur][j]dp[cur][j-1]有关。(0<=cur < i)

如果nums[cur]nums[i]相同,那么dp[i][j]的值等于max(dp[i][j], dp[cur][j] + 1)。即,可以在nums[cur]为结尾的子序列加上nums[i]

如果nums[cur]nums[i]不同,那么dp[i][j]的值等于max(dp[i][j], dp[cur][j-1] + 1)。即,不可以在nums[cur]为结尾的子序列加上nums[i]

最后,我们可以返回dp数组中最大值,即为最长的好子序列的长度。

代码实现

Go版本:

func maximumLength(nums []int, k int) int {n := len(nums)dp := make([][]int, n)for i := range dp {dp[i] = make([]int, k+1)}res := 0for i := 0; i < n; i++ {dp[i][0] = 1for j := 0; j <= k&&j<=i; j++ {for cur := 0; cur < i; cur++ {if nums[i] == nums[cur] {dp[i][j]=max(dp[i][j],dp[cur][j]+1)}else{if(j-1>=0){dp[i][j]=max(dp[i][j],dp[cur][j-1]+1)}}}res = max(res, dp[i][j])}}return res
}

Python版本:

class Solution(object):def maximumLength(self, nums, k):n = len(nums)dp = [[0] * (k + 1) for _ in range(n)]res = 0for i in range(n):dp[i][0] = 1for j in range(min(k, i) + 1):for cur in range(i):if nums[i] == nums[cur]:dp[i][j] = max(dp[i][j], dp[cur][j] + 1)else:if j - 1 >= 0:dp[i][j] = max(dp[i][j], dp[cur][j - 1] + 1)res = max(res, dp[i][j])return res

C++版本:

class Solution {
public:int maximumLength(vector<int>& nums, int k) {int n = nums.size();vector<vector<int>> dp(n, vector<int>(k + 1, 0));int res = 0;for (int i = 0; i < n; i++) {dp[i][0] = 1;for (int j = 0; j <= k && j <= i; j++) {for (int cur = 0; cur < i; cur++) {if (nums[i] == nums[cur]) {dp[i][j] = max(dp[i][j], dp[cur][j] + 1);} else {if (j - 1 >= 0) {dp[i][j] = max(dp[i][j], dp[cur][j - 1] + 1);}}}res = max(res, dp[i][j]);}}return res;}
};

这篇关于leetcode:3176 求出最长好子序列 使用动态规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1144245

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

Makefile简明使用教程

文章目录 规则makefile文件的基本语法:加在命令前的特殊符号:.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具,常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma