马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
【LetMeFly】3176.求出最长好子序列 I：动态规划（DP）
力扣题目链接：https://leetcode.cn/problems/find-the-maximum-length-of-a-good-subsequence-i/
给你一个整数数组 nums 和一个 非负 整数 k 。假如一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq != seq[i + 1] ，那么我们称这个整数序列为 好 序列。
请你返回 nums 中 好 子序列 的最长长度
示例 1：
输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：
最长好子序列为 [1,2,1,1,3] 。
示例 2：
输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最长好子序列为 [1,2,3,4,5,1] 。
提示：
- 1 <= nums.length <= 500
- 1 <= nums <= 109
- 0 <= k <= min(nums.length, 25)
解题方法：动态规划
使用一个动态规划数组 d p dp dp，此中 d p [ i ] [ l ] dp[l] dp[l]代表数组前 i i i个元素的不超过 l l l个相邻不同的好子序列的最大长度。
初始值 d p [ i ] [ 0 ] = 1 dp[0]=1 dp[0]=1，其余值默认为 − 1 -1 −1就行，转移方程：
d p [ i ] [ l ] = min { d p [ i ] [ l ] d p [ j ] [ l ] + 1 if n u m s [ i ] = n u m s [ j ] d p [ j ] [ l − 1 ] + 1 if n u m s [ i ] ≠ n u m s [ j ] and l > 0 dp[l] = \min \begin{cases} dp[l] & \\ dp[j][l] + 1 & \text{ if } nums=nums[j]\\ dp[j][l - 1] + 1 & \text{ if } nums \neq nums[j] \text{ and } l \gt 0 \end{cases} dp[l]=min⎩ ⎨ ⎧dp[l]dp[j][l]+1dp[j][l−1]+1 if nums=nums[j] if nums=nums[j] and l>0
三层循环，第一层用 i i i从 0 0 0到 l e n ( n u m s ) − 1 len(nums)-1 len(nums)−1，第二层用 l l l从 0 0 0到 k k k，第三层用 j j j从 0 0 0到 i − 1 i-1 i−1。
- 时间复杂度 O ( l e n ( n u m s ) 2 × k ) O(len(nums)^2\times k) O(len(nums)2×k)
- 空间复杂度 O ( l e n ( n u m s ) × k ) O(len(nums)\times k) O(len(nums)×k)
更低复杂度请见下一题：求出最长好子序列 II
AC代码
C++
- class Solution {
- public:
- int maximumLength(vector<int>& nums, int k) {
- vector<vector<int>> dp(nums.size(), vector<int>(k + 1, -1));
- for (int i = 0; i < nums.size(); i++) {
- dp[i][0] = 1;
- for (int l = 0; l <= k; l++) {
- for (int j = 0; j < i; j++) {
- int diff = nums[i] != nums[j];
- if (l - diff >= 0) {
- dp[i][l] = max(dp[i][l], dp[j][l - diff] + 1);
- }
- }
- }
- }
- int ans = 0;
- for (int i = 0; i < nums.size(); i++) {
- for (int l = 0; l <= k; l++) {
- ans = max(ans, dp[i][l]);
- }
- }
- return ans;
- }
- };
- from typing import List
- class Solution:
- def maximumLength(self, nums: List[int], k: int) -> int:
- dp = [[-1] * (k + 1) for _ in range(len(nums))]
- for i in range(len(nums)):
- dp[i][0] = 1
- for l in range(k + 1):
- for j in range(i):
- diff = int(nums[i] != nums[j])
- if l - diff >= 0:
- dp[i][l] = max(dp[i][l], dp[j][l - diff] + 1)
- return max(max(dp[i]) for i in range(len(nums)))
Tisfy：https://letmefly.blog.csdn.net/article/details/141992543
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
