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

相关文章

postgresql使用UUID函数的方法

《postgresql使用UUID函数的方法》本文给大家介绍postgresql使用UUID函数的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录PostgreSQL有两种生成uuid的方法。可以先通过sql查看是否已安装扩展函数,和可以安装的扩展函数

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

如何使用Lombok进行spring 注入

《如何使用Lombok进行spring注入》本文介绍如何用Lombok简化Spring注入,推荐优先使用setter注入,通过注解自动生成getter/setter及构造器,减少冗余代码,提升开发效... Lombok为了开发环境简化代码,好处不用多说。spring 注入方式为2种,构造器注入和setter

MySQL中比较运算符的具体使用

《MySQL中比较运算符的具体使用》本文介绍了SQL中常用的符号类型和非符号类型运算符,符号类型运算符包括等于(=)、安全等于(=)、不等于(/!=)、大小比较(,=,,=)等,感兴趣的可以了解一下... 目录符号类型运算符1. 等于运算符=2. 安全等于运算符<=>3. 不等于运算符<>或!=4. 小于运

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4

Python 字典 (Dictionary)使用详解

《Python字典(Dictionary)使用详解》字典是python中最重要,最常用的数据结构之一,它提供了高效的键值对存储和查找能力,:本文主要介绍Python字典(Dictionary)... 目录字典1.基本特性2.创建字典3.访问元素4.修改字典5.删除元素6.字典遍历7.字典的高级特性默认字典

使用Python构建一个高效的日志处理系统

《使用Python构建一个高效的日志处理系统》这篇文章主要为大家详细讲解了如何使用Python开发一个专业的日志分析工具,能够自动化处理、分析和可视化各类日志文件,大幅提升运维效率,需要的可以了解下... 目录环境准备工具功能概述完整代码实现代码深度解析1. 类设计与初始化2. 日志解析核心逻辑3. 文件处

一文详解如何使用Java获取PDF页面信息

《一文详解如何使用Java获取PDF页面信息》了解PDF页面属性是我们在处理文档、内容提取、打印设置或页面重组等任务时不可或缺的一环,下面我们就来看看如何使用Java语言获取这些信息吧... 目录引言一、安装和引入PDF处理库引入依赖二、获取 PDF 页数三、获取页面尺寸(宽高)四、获取页面旋转角度五、判断

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

Spring StateMachine实现状态机使用示例详解

《SpringStateMachine实现状态机使用示例详解》本文介绍SpringStateMachine实现状态机的步骤,包括依赖导入、枚举定义、状态转移规则配置、上下文管理及服务调用示例,重点解... 目录什么是状态机使用示例什么是状态机状态机是计算机科学中的​​核心建模工具​​,用于描述对象在其生命