→ yam276: 我DP好爛 這題想好久 07/21 15:50
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：
--------------------------------------------------
class Solution {
public int findNumberOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
int[] count = new int[n];
int res = 0;
int maxLen = 1;
for (int i = 0; i < n; i++) {
dp[i] = 1;
count[i] = 1;
for (int j = i - 1; j >= 0; j--) {
if (nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
count[i] = count[j];
} else if (dp[j] + 1 == dp[i]) {
count[i] += count[j];
}
}
}
if (dp[i] > maxLen) {
maxLen = dp[i];
res = count[i];
} else if (dp[i] == maxLen) {
res += count[i];
}
}
return res;
}
}
--------------------------------------------------
--
https://i.imgur.com/YPBHGGE.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1689923800.A.9F9.html
※ 編輯: Rushia (122.100.75.86 臺灣), 07/21/2023 15:20:02