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

相关文章

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

Qt中QUndoView控件的具体使用

《Qt中QUndoView控件的具体使用》QUndoView是Qt框架中用于可视化显示QUndoStack内容的控件,本文主要介绍了Qt中QUndoView控件的具体使用,具有一定的参考价值,感兴趣的... 目录引言一、QUndoView 的用途二、工作原理三、 如何与 QUnDOStack 配合使用四、自

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

使用Python构建一个Hexo博客发布工具

《使用Python构建一个Hexo博客发布工具》虽然Hexo的命令行工具非常强大,但对于日常的博客撰写和发布过程,我总觉得缺少一个直观的图形界面来简化操作,下面我们就来看看如何使用Python构建一个... 目录引言Hexo博客系统简介设计需求技术选择代码实现主框架界面设计核心功能实现1. 发布文章2. 加

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

使用Python开发一个带EPUB转换功能的Markdown编辑器

《使用Python开发一个带EPUB转换功能的Markdown编辑器》Markdown因其简单易用和强大的格式支持,成为了写作者、开发者及内容创作者的首选格式,本文将通过Python开发一个Markd... 目录应用概览代码结构与核心组件1. 初始化与布局 (__init__)2. 工具栏 (setup_t

Python虚拟环境终极(含PyCharm的使用教程)

《Python虚拟环境终极(含PyCharm的使用教程)》:本文主要介绍Python虚拟环境终极(含PyCharm的使用教程),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录一、为什么需要虚拟环境?二、虚拟环境创建方式对比三、命令行创建虚拟环境(venv)3.1 基础命令3

Python Transformer 库安装配置及使用方法

《PythonTransformer库安装配置及使用方法》HuggingFaceTransformers是自然语言处理(NLP)领域最流行的开源库之一,支持基于Transformer架构的预训练模... 目录python 中的 Transformer 库及使用方法一、库的概述二、安装与配置三、基础使用:Pi

关于pandas的read_csv方法使用解读

《关于pandas的read_csv方法使用解读》:本文主要介绍关于pandas的read_csv方法使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录pandas的read_csv方法解读read_csv中的参数基本参数通用解析参数空值处理相关参数时间处理相关

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例