LeetCode_动态规划_中等_673.最长递增子序列的个数

我就是我 2023-10-06 23:42 23阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数。

注意这个数列必须是**严格递增**的。

**示例 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。

**提示：**  
1 <= nums.length <= 2000  
\-106 <= nums\[i\] <= 106

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/number-of-longest-increasing-subsequence

## 2.思路 ##

（1）动态规划  
思路参考[本题官方题解][Link 1]。

此题是[300.最长递增子序列][300.]这题的进阶版，可以先了解该题的做法，然后再来看本题。如果想要求最长递增子序列的个数，那么需要在知道递增子序列的最长长度是多少的前提下，来计算该长度的递增子序列的个数。

① 定义 dp 数组，dp\[i\] 表示数组 nums 中以 nums\[i\] 结尾的最长递增子序列的长度。同时还定义数组 cnt，cnt\[i\] 表示以 nums\[i\] 结尾的最长递增子序列的个数。**设递增子序列的最长长度为 maxLen，那么本题的答案就为所有满足 dp\[i\] = maxLen 的 i 所对应的 cnt\[i\] 之和。**

② 由[300.最长递增子序列][300.]这题的分析可知，状态转移方程为：

if(nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1); // i > j ≥ 0

而对于 cnt\[i\]，在计算 dp\[i\] 的同时来统计 cnt\[i\] 的值。

## 3.代码实现（Java） ##

//思路1————动态规划
    class Solution {
        
        public static int findNumberOfLIS(int[] nums) {
        
            int length = nums.length;
            // dp[i] 表示数组 nums 中以 nums[i] 结尾的最长连续递增子序列的长度
            int[] dp = new int[length];
            // cnt[i] 表示数组 nums 中以 nums[i] 结尾的最长递增子序列的个数
            int[] cnt = new int[length];
            Arrays.fill(dp, 1);
            Arrays.fill(cnt, 1);
            // maxLen 记录最大长度
            int maxLen = 1;
            // res 记录最长递增子序列的个数
            int res = 0;
            for (int i = 0; i < length; i++) {
        
                for (int j = 0; j < i; j++) {
        
                    if (nums[i] > nums[j]) {
        
                        if (dp[i] < dp[j] + 1) {
        
                            dp[i] = dp[j] + 1;
                            cnt[i] = cnt[j];
                        } else if (dp[i] == dp[j] + 1){
        
                            cnt[i] += cnt[j];
                        }
                    }
                }
                if (dp[i] == maxLen) {
        
                    res += cnt[i];
                } else if (dp[i] > maxLen) {
        
                    maxLen = dp[i];
                    res = cnt[i];
                }
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/number-of-longest-increasing-subsequence/solution/zui-chang-di-zeng-zi-xu-lie-de-ge-shu-by-w12f/
[300.]: https://blog.csdn.net/weixin_43004044/article/details/122357063