Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-07-21 15:16:38
https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/
673. Number of Longest Increasing Subsequence
给你一个阵列找出这个阵列的最长递增子序列共有几个,递增为严格递增。
Example 1:
Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1,
3, 5, 7].
Example 2:
Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of the longest increasing subsequence is 1, and there
are 5 increasing subsequences of length 1, so output 5.
思路:
1. [300. Longest Increasing Subsequence] 这题的延伸版本,原题目只要求长度
现在要求有几个,dp 的思路是如果我们知道 i 之前的所有最长递增子序列长度,
则 dp[i] 的最长子序列长度只需要找满足 nums[j] < nums[i] 且 j < i 的 j
并取 dp[j] 的最大值加一就是 dp[i] 的 LIS。
2.只需要把原题目在算 dp 的时候顺便统计这个长度的序列有几个即可,当遇到更大
的长度就更新长度并重置当前计数,遇到一样的长度则累加。
Java Code:
作者: yam276 ('_')   2023-07-21 15:50:00
我DP好烂 这题想好久

Links booklink

Contact Us: admin [ a t ] ucptt.com