673. 最长递增子序列的个数

叁歲伎倆 2022-09-12 03:55 135阅读 0赞

#### 2021-09-20 LeetCode每日一题 ####

链接：[https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/][https_leetcode-cn.com_problems_number-of-longest-increasing-subsequence]

标签：**数组、动态规划**

> 题目

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

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

注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

> 分析

求解最长递增子序列的长度，这个可以看[第300题][300]。关键这里我们需要求最长递增子序列的个数，还记得在第300题的时候，dp数组的定义是dp\[i\]表示以nums\[i\]结尾的最长递增子序列的长度。对于此题，我们还需要增加一个数组com\[i\]，定义com\[i\]表示以nums\[i\]结尾的能组成最长递增子序列的路径数量。对于任意com\[i\]，初始化为1.

比如\[1,3,5,4,7\]，dp\[4\] = 4，com\[4\] = 2。因为可以通过\[1, 3, 5 ,7\]和\[1, 3, 4, 7\]这两条路径组成最长递增子序列。最后只需要把dp\[i\]的值等于max时对于的com\[i\]累加就是最长递增子序列的个数。

求解dp\[i\]的方式和第300题一样，求解com\[i\]的时候，dp\[i\]的值有更新，那么说明找到一个新的以nums\[i\]结尾的最长递增子序列，那么只需要更新dp\[i\]的值并且com\[i\]继承之前的com\[j\]。如果dp\[j\] +1 == dp\[i\]，则说明找到了一个新的路径，则com\[i\] = com\[i\] + com\[j\]。

具体看代码。

> 编码

class Solution { 
        public int findNumberOfLIS(int[] nums) { 
            int len = nums.length;
            int[] dp = new int[len];
            // 以nums[i]结尾的最长递增子序列的路径数
            int[] vals = new int[len];
            Arrays.fill(dp, 1);
            Arrays.fill(vals, 1);
            int res = 0, max = 1;
    
            for (int i = 0; i < nums.length; i++) { 
                for (int j = 0; j < i; j++) { 
                    if (nums[i] > nums[j]) { 
                        // 出现了一个以nums[i]结尾的新的递增子序列
                        if (dp[i] < dp[j] + 1) { 
                            dp[i] = dp[j] + 1;
                            vals[i] = vals[j];
                        } else if (dp[i] == dp[j] + 1) { 
                            // 以nums[i]结尾的递增子序列的长度不变，多了一条新路径
                            vals[i] += vals[j];
                        }
                    }
                }
                max = Math.max(max, dp[i]);
            }
    
            for (int i = 0; i < len; i++) { 
                if (dp[i] == max) { 
                    res += vals[i];
                }
            }
            return res;
        }
    }

![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56eD5aS05ZOl57yW56iL_size_20_color_FFFFFF_t_70_g_se_x_16]

[https_leetcode-cn.com_problems_number-of-longest-increasing-subsequence]: https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/
[300]: https://leetcode-cn.com/problems/longest-increasing-subsequence/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56eD5aS05ZOl57yW56iL_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d2d6762d0ae941eab85fefe430ef6043.png