本文主要是介绍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 求出最长好子序列 使用动态规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!