题目描述
给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 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位有符号整数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法1 – Top-down
这道题目是第300题的升级，那道题目仅要求找出最长递增子序列(LIS)的长度，而这道题目需要统计LIS有多少个。为了求出数组nums的LIS个数，我们先要求得最长递增子序列的长度maxLen。然后扫描nums数组，统计LIS长度为maxLen的个数。
首先我们实现一个函数，求数组nums的LIS的长度（参考300题的Top-down解法）。我们定义函数lengthOfLIS(int[] nums, int n)，表示计算数组nums前n个元素(n从1开始，包含第n个且必须使用第n个元素)能够形成LIS的长度。例如我们有nums = [1,2,3,2,2]，那么lengthOfLIS(nums, 4) = 2而不是3，因为我们必须使用nums[4]。
为了求num前n个元素的LIS，我们可以使用递归来解决。对于长度n，我们向前寻找某一元素i，使其满足nums[n] > nums[i]（递增的定义），然后递归调用lengthOfLIS(nums, i)，即求解nums数组前i个元素的LIS。代码如下：
private int lengthOfLIS(int[] nums, int n) {
int maxLen = 1;
for (int i = 0; i < n; i++) {
if (nums[n-1] > nums[i-1]) {
maxLen = Math.max(maxLen, lengthOfLIS(nums, i) + 1);
}
}
return maxLen;
}
下一步，我们定义函数count(int[] nums, int n)用于计算nums前n个元素（n从1开始，包含第n个且必须使用第n个元素）构成的LIS长度为maxLen的递增子序列数量。它会调用上面实现的函数lengthOfLIS(nums, n)。在这里我们举一个例子，nums = [1,3,2,4,5]，则
count(nums, 1) = 1，因为前1个元素为[1]，maxLen = lengthOfLIS(nums, 1) = 1，只能找到1个长度为1的LIS：[1].
count(nums, 2) = 1, 因为前2个元素为[1,3]，maxLen = lengthOfLIS(nums, 2) = 2，只能找到1个长度为2的LIS：[1,3]
count(nums, 3) = 1, 因为前3个元素为[1,3,2]，maxLen = lengthOfLIS(nums, 3) = 2，只能找到1个长度为2的LIS：[1,2]。你可能会疑问，为什么[1,3]不计算在内？因为前面说过，count(nums, n)的定义是必须使用第n个元素，即num[3 – 1] = 2。
count(nums, 4) = 2，因为前4个元素为[1,3,2,4]，maxLen = lengthOfLIS(nums, 4) = 3，能找到2个长度为3的LIS：[1,3,4]和[1,2,4]。
count(nums, 5) = 2，因为前5个元素为[1,3,2,4,5]，maxLen = lengthOfLIS(nums, 5) = 4，能找到2个长度为4的LIS：[1,3,4,5]和[1,2,4,5]。
下面，我们看一下count(nums, n)是如何实现的：
public int count(int[] nums, int n) {
int c = 0;
int maxLen = lengthOfLIS(nums, n);
for (int i = 1; i <= n; i++) {
if (nums[n - 1] > nums[i - 1] && lengthOfLIS(nums, i) + 1 == maxLen) {
c += count(nums, i);
}
}
return c == 0 ? 1 : c;
}
我们首先从n的前面的寻找位置i，查看是否存在num[i] < nums[n]（递增定义）。如果找到这样的i，我们计算lengthOfLIS(nums, i) + 1是否与maxLen相等（lengthOfLIS(nums, i) + 1表示将第n个元素接续到子序列后面）。如果找到这样的位置i，我们调用c += count(nums, i)统计有多少个LIS的长度为maxLen – 1。最后，如果找不到长度为maxLen – 1的子序列就返回1。这表示该LIS自己成为独立的一个子序列，例如nums = [4,3,2,1]，很明显每一个元素的前面都找不到比他小的元素，所以每个元素自己独立成为一个LIS。
最后，我们将count和lengthOfLIS组合起来调用，就能求得问题的答案：最长LIS的个数。
public int findNumberOfLIS(int[] nums) {
int maxLen = 0;
// 先求得整个数组nums的LIS的长度maxLen
for (int i = 1; i <= nums.length; i++)
maxLen = Math.max(maxLen, lengthOfLIS(nums, i));
// 统计长度为maxLen的数量
int ans = 0;
for (int i = 1; i <= nums.length; i++) {
if (lengthOfLIS(nums, i) == maxLen) {
ans += count(nums, i);
}
}
return ans;
}
到这里我们就实现了Top-down解法，但是这个实现并不能AC。因为使用递归会造成重复求解相同的子问题，当问题的规模扩大后运行时间会相当长。我们可以使用len[|nums| + 1]来存储函数lengthOfLIS计算过的解；使用另一个数组count[|nums| + 1]来存储函数count计算过的解。全部代码如下：
class Solution {
private int[] len;
private int[] count;
public int findNumberOfLIS(int[] nums) {
int maxLen = 0;
len = new int[nums.length + 1];
count = new int[nums.length + 1];
for (int i = 1; i <= nums.length; i++)
maxLen = Math.max(maxLen, lengthOfLIS(nums, i));
int ans = 0;
for (int i = 1; i <= nums.length; i++) {
if (lengthOfLIS(nums, i) == maxLen) {
ans += count(nums, i);
}
}
return ans;
}
private int lengthOfLIS(int[] nums, int n) {
if (len[n] > 0)
return len[n];
int maxLen = 1;
for (int i = 1; i <= n; i++) {
if (nums[n - 1] > nums[i - 1]) {
maxLen = Math.max(maxLen, lengthOfLIS(nums, i) + 1);
}
}
len[n] = maxLen;
return maxLen;
}
public int count(int[] nums, int n) {
if (count[n] > 0)
return count[n];
int c = 0;
int maxLen = lengthOfLIS(nums, n);
for (int i = 1; i <= n; i++) {
if (nums[n - 1] > nums[i - 1] && lengthOfLIS(nums, i) + 1 == maxLen) {
c += count(nums, i);
}
}
if (c == 0)
c = 1;
count[n] = c;
return c;
}
}
解法2 – Bottom-up
我们定义数组dp[|nums| + 1]，dp[n]表示对于nums的前n个元素（n > 0，包含第n个且必须使用第n个元素）形成的LIS长度。dp数组开始时所有元素都为1，表示每个元素都是一个LIS，之后我们会把每个LIS拼接起来成为更长的LIS。
定义数组count[|nums| + 1]，count[n]表示对于nums的前n个元素形成的长度为dp[n]的LIS的数量。count数组初始值也所有元素都为1。
简而言之dp用来存放LIS长度，count用来存放该长度下LIS的数量。接下来我们怎样更新数组dp和count呢？
if (nums[i - 1] > nums[j - 1]) {
if (dp[j] >= dp[i]) { // 分支1
dp[i] = dp[j] + 1;
count[i] = count[j];
} else if (dp[j] + 1 == dp[i]) { // 分支2
count[i] += count[j];
}
}
我们来举一个例子，nums = [1,3,2,4,5]；初始时dp = [1,1,1,1,1]；count = [1,1,1,1,1]；i = 1~|nums|, 1 <= j < i。
分支1：
LIS: [1], LIS: [3] -> LIS: [1, 3]
当i = 2, j = 1时，nums[1] > nums[0]成立，dp[1] == dp[2]，更新dp[2] = dp[1] + 1，count[2] = count[1]。物理意义是：在i的前面找到了一个以nums[j – 1]结尾的LIS，将nums[i]接到这个子序列后面形成更长的LIS。所以执行dp[i] = dp[j] + 1，表示多了一个元素num[i – 1]；执行count[i] = count[j]，因为拼接后形成的只是一个更长的子序列，LIS的数量和count[j]一致。
分支2
LIS: [1, 3]-\ [1, 3, 4] （1）
\LIS: [4] -> LIS:
/ [1, 2, 4] （2）
LIS: [1, 2]-/
（1）当i = 4，j = 2时, dp[j] = 2, count[j] = 1；nums[3] > nums[1]，且dp[2] > dp[4]成立，更新dp[4] = dp[2] + 1 = 3，count[4] = count[2] = 1。形成新的LIS = [1, 3, 4]。
（2）当i = 4，j = 3时，dp[j] = 2，count[j] = 1；nums[3] > nums[2]，成立且dp[3] + 1 == dp[4]。那么我们执行count[4] += count[3]，此时我们找到了两个LIS = [1, 3, 4]和[1, 2, 4]。
全部代码如下：
class Solution {
public int findNumberOfLIS(int[] nums) {
int[] dp = new int[nums.length + 1];
int[] count = new int[nums.length + 1];
int maxLIS = 1;
Arrays.fill(dp, 1);
Arrays.fill(count, 1);
for (int i = 1; i <= nums.length; i++) {
for (int j = 1; j < i; j++) {
if (nums[i - 1] > nums[j - 1]) {
if (dp[j] >= dp[i]) {
dp[i] = dp[j] + 1;
count[i] = count[j];
} else if (dp[j] + 1 == dp[i]) {
count[i] += count[j];
}
}
}
maxLIS = Math.max(maxLIS, dp[i]);
}
int ans = 0;
for (int i = 1; i <= nums.length; i++) {
if (dp[i] == maxLIS) {
ans += count[i];
}
}
return ans;
}
}