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

题目描述

给定一个未排序的整数数组 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 -10^6 <= nums[i] <= 10^6

题目解析

好的，没问题！我是 AlgoMooc 的算法老师。我们一起来搞定这道题，保证让你听完之后觉得“原来这么简单！”

---

题目在说什么

我们先来用大白话翻译一下题目。

题目给了你一个乱序的数字列表，比如 [1,3,5,4,7]。你需要找出两样东西：

1. 最长递增子序列的长度：在这个列表里，能挑出几个数字，它们从左到右是严格一个比一个大，并且这个序列要尽可能长。注意，你可以跳着选，不用连续。比如 [1,3,5,7] 就是一个，长度是4。[1,3,4,7] 也是，长度也是4。所以最长长度是4。 2. 这个最长长度的序列有多少个：刚才我们找到了两个长度是4的序列，所以答案是2。

再看第二个例子 [2,2,2,2,2]，所有数字都一样，没有严格递增的序列。那最长的递增子序列就是它自己（单个数字），长度是1。这样的序列有5个（每个2自己），所以答案是5。

总结一下：题目就是让你先找到最长能有多长，再数一数，能组成这个最长长度的方案有多少种。

---

思路是怎么来的

很多新手看到“子序列”和“个数”就头大。别怕，我们用一个生活化的例子来想。

想象一下你在玩一个“搭积木”游戏。

• 每个数字 nums[i] 都是一块积木，上面写着数字。
• 你的任务是用这些积木搭出越来越高的塔（递增序列）。
• 你只能把数字小的积木放在下面，数字大的积木放在上面。
• 你可以跳过一些积木不用。

现在，我们想知道：以每一块积木为塔顶，能搭出的最高塔有多高？以及，有多少种不同的搭法能搭出这个高度？

比如，我们看 [1,3,5,4,7] 这个列表。

1. 第一块积木 `1`：它自己就是一座塔，高度为1。搭法只有1种（就是它自己）。 2. 第二块积木 `3`：它比 1 大，所以可以放在 1 的上面。这样塔的高度就变成了 1 的高度 + 1 = 2。搭法就是继承 1 的搭法，只有1种。 3. 第三块积木 `5`：它比前面的 1 和 3 都大。它可以放在 1 上面（高度变成2），也可以放在 3 上面（高度变成3）。显然，放在 3 上面能搭出更高的塔（高度3）。所以，以 5 为顶的最高塔高度是3，搭法继承自 3，只有1种。 4. 第四块积木 `4`：它比 1 和 3 大，但比 5 小。它可以放在 1 上面（高度2），也可以放在 3 上面（高度3）。所以，以 4 为顶的最高塔高度也是3，搭法继承自 3，只有1种。 5. 第五块积木 `7`：它比前面所有都大。它可以放在 1（高度2）、3（高度3）、5（高度4）、4（高度4）上面。放在 5 或 4 上面，都能得到高度4的塔。关键点来了：搭法不是继承一个，而是把能搭出高度3的那些积木（5 和 4）的搭法加起来。5 有1种搭法，4 有1种搭法，所以以 7 为顶、高度为4的搭法就有 1+1=2 种。

最后，我们看看所有积木里，最高塔的高度是4（5 和 7 都能搭出高度4）。然后我们把所有能搭出高度4的积木的搭法个数加起来：5 有1种，7 有2种，总共3种？等等，我们之前说答案是2。哪里出错了？

注意！ 以 5 为顶的塔是 [1,3,5]，高度是3，不是4！我上面说错了。我们重新来：

• 以 1 为顶：高度1，搭法1
• 以 3 为顶：高度2（[1,3]），搭法1
• 以 5 为顶：高度3（[1,3,5]），搭法1
• 以 4 为顶：高度3（[1,3,4]），搭法1
• 以 7 为顶：它可以放在 5（高度3）和 4（高度3）上面，得到高度4。搭法 = 5的搭法 + 4的搭法 = 1 + 1 = 2。

所以，最高高度是4，只有 7 这个积木能搭出这个高度，搭法有2种。答案就是2。

这个“搭积木”的过程，就是动态规划的核心思想。 我们不需要一次算出所有东西，而是从第一个元素开始，一步步地记录下“以当前元素结尾”的最优结果（高度和搭法），然后后面的元素可以利用前面的结果。

---

代码逐步拆解

现在，我们来看代码，把刚才的思路翻译成计算机语言。

public class Solution {  
    public int findNumberOfLIS(int[] nums) {

        int n = nums.length;

        // dp[i]：以 nums[i] 这个数字为塔顶，能搭出的最高塔的高度。
        int[] dp = new int[n];
        // count[i]：以 nums[i] 为塔顶，能搭出 dp[i] 这个高度的塔，有多少种不同的搭法。
        int[] count = new int[n];