欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 房产 > 家装 > LeetCode: 673.最长子序列的数量 动态规划 时间复杂度O(n*n)

LeetCode: 673.最长子序列的数量 动态规划 时间复杂度O(n*n)

2025/2/23 7:12:38 来源:https://blog.csdn.net/weixin_60214397/article/details/142106119  浏览:    关键词:LeetCode: 673.最长子序列的数量 动态规划 时间复杂度O(n*n)

673.最长子序列的数量

LeetCode原题连接 673. 最长子序列的数量

题目描述

给定一个未排序的整数数组,找到最长递增子序列的个数。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列,分别是 [1, 3, 4, 7] 和 [1, 3, 5, 7]。

示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1,并且存在5个子序列的长度为1,因此输出5。

提示:

  • 0 <= nums.length <= 2000
  • -10^6 <= nums[i] <= 10^6

题目解析

这道题是 Leetcode 300. 最长递增子序列的进阶版本,我们不仅要找到最长子序列,还要找到最长子序列的个数。写该题之间建议先完成 Leetcode 300. 最长递增子序列。我们在以前的博客中已经详细介绍过寻找最长递增子序列的算法。

接下来,我们对算法进行改造,以解决这个更为复杂的问题。

在原来的算法中,我们维护一个数组dp[i],表示nums中前i个元素的最长递增子序列的长度。我们对dp数组进行更新,具体的更新规则如下:

  1. 如果nums[i] > nums[j], 且dp[j] + 1 > dp[i], 则dp[i] = dp[j] + 1,0 <= j < i。
  2. 否则,dp[i] = dp[i]

现在,我们不仅需要知道,nums中前i个元素的最长递增子序列的长度,还需要知道,nums中前i个元素的最长递增子序列的个数。

我们可以维护一个数组count[i],表示nums中前i个元素的最长递增子序列的个数。我们对count数组进行更新,具体的更新规则如下:

  1. 如果nums[i] > nums[j], 且dp[j] + 1 == dp[i], 则count[i] += count[j],0 <= j < i。这表示当前长度为dp[i]的最长递增子序列,可以由前j个元素的最长递增子序列延伸得到。
  2. 如果nums[i] > nums[j], 且dp[j] + 1 > dp[i],则count[i] = count[j]。这表示当前dp[i]并不是以nums[i]结尾的最长递增子序列,最长递增子序列长度应该更新为 dp[j] + 1。那么count[i] = count[j],表示当前长度为dp[j]+1的最长递增子序列,只能由前j个元素的最长递增子序列延伸得到。

这样,我们就得到了nums中前i个元素的最长递增子序列长度和对应的最长子序列的个数。

接下来,只要将dp数组中最大的元素(即最长子序列的长度),在count数组中对应的值累加起来,就可以得到nums中最长递增子序列的个数。

复杂度分析

  • 时间复杂度: O ( n 2 ) O(n^2) O(n2),其中 n 是数组 nums 的长度。
  • 空间复杂度: O ( n ) O(n) O(n),其中 n 是数组 nums 的长度。

代码实现

Go版本

func findNumberOfLIS(nums []int) int {n:=len(nums)  // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度 dp:=make([]int,n) // cnt[i] 表示以 nums[i] 结尾的、长度为 dp[i] 的递增子序列的个数 cnt:=make([]int,n)maxLen:=1cnt[0]=1dp[0]=1for i:=1;i<n;i++{cnt[i]=1dp[i]=1for j:=0;j<i;j++{if(nums[i]>nums[j]){if(dp[i]==dp[j]+1){cnt[i]+=cnt[j]}else if(dp[i]<dp[j]+1){cnt[i]=cnt[j]dp[i]=max(dp[i],dp[j]+1)}}}maxLen=max(maxLen,dp[i])}res:=0for i:=0;i<n;i++{if(dp[i]==maxLen){res+=cnt[i]}}return res
}

Python版本

class Solution(object):def findNumberOfLIS(self, nums):n = len(nums)  dp = [1] * n   # dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度 cnt = [1] * n  # cnt[i] 表示以 nums[i] 结尾的、长度为 dp[i] 的递增子序列的个数max_len = 1  for i in range(1, n):  for j in range(i):  if nums[i] > nums[j]:  if dp[i] == dp[j] + 1:  cnt[i] += cnt[j]  elif dp[i] < dp[j] + 1:  dp[i] = dp[j] + 1  cnt[i] = cnt[j]  max_len = max(max_len, dp[i])  res = 0  for i in range(n):  if dp[i] == max_len:  res += cnt[i]  return res

C++版本

class Solution {
public:int findNumberOfLIS(vector<int>& nums) {int n = nums.size();  vector<int> dp(n, 1);  // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度  vector<int> cnt(n, 1); // cnt[i] 表示以 nums[i] 结尾的、长度为 dp[i] 的递增子序列的个数  int max_len = 1;  for (int i = 1; i < n; ++i) {  for (int j = 0; j < i; ++j) {  if (nums[i] > nums[j]) {  if (dp[i] == dp[j] + 1) {  cnt[i] += cnt[j];  } else if (dp[i] < dp[j] + 1) {  dp[i] = dp[j] + 1;  cnt[i] = cnt[j];  }  }  }  max_len = max(max_len, dp[i]);  }  int res = 0;  for (int i = 0; i < n; ++i) {  if (dp[i] == max_len) {  res += cnt[i];  }  }  return res;  }
};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词