【LeetCode 动态规划专项】最长递增子序列的个数（673）

最新推荐文章于 2025-05-28 20:00:00 发布

TakingCoding4Granted

最新推荐文章于 2025-05-28 20:00:00 发布

阅读量391

点赞数 3

分类专栏： LeetCode 文章标签： leetcode 动态规划算法

本文链接：https://blog.csdn.net/weixin_37780776/article/details/120240329

版权

LeetCode 专栏收录该内容

140 篇文章

订阅专栏

文章目录

1. 题目
1.1 示例
1.2 说明
1.3 提示
1.4 进阶

2. 解法一（动态规划）
2.1 分析
2.1.1 定义状态
2.1.2 初始化状态
2.1.3 状态转移
2.1.4 返回结果

2.2 解答
2.3 复杂度

3. 解法二（耐心排序）
3.1 分析
3.2 解答
3.3 复杂度

1. 题目

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

1.1 示例

示例 $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.2 说明

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

1.3 提示

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

1.4 进阶

2. 解法一（动态规划）

2.1 分析

作者： edelweisskoko

2.1.1 定义状态

dp[i]：到 nums[i] 为止的最长递增子序列长度；
count[i]：到 nums[i] 为止的最长递增子序列个数。

2.1.2 初始化状态

dp = [1] * n：代表最长递增子序列的长度至少为 $1$ ；
count = [1] * n：代表最长递增子序列的个数至少为 $1$ 。

2.1.3 状态转移

对于每一个数 nums[i]，看在它之前的数 nums[j] ( $\le j \lt i$ )是否比当前数 nums[i] 小：

如果 nums[i] > nums[j]，那么相当于到 nums[j] 为止的最长递增子序列长度到 nums[i] 增加了 $1$ ，到 nums[i] 为止的最长递增子序列长度就变成了 dp[i] = dp[j] + 1 ；
但是因为满足 nums[i] > nums[j] 的 nums[j] 不止一个，dp[i] 应该取这些 dp[j] + 1 的最大值，并且这些 dp[j] + 1 还会有相等的情况，一旦相等，到 nums[i] 为止的最长递增子序列个数就应该增加了。因此，具体的状态转移如下，在 nums[i] > nums[j] 的大前提下：
- 如果 dp[j] + 1 > dp[i] ，说明最长递增子序列的长度增加了，dp[i] = dp[j] + 1，长度增加，数量不变 count[i] = count[j] ；
- 如果 dp[j] + 1 == dp[i]，说明最长递增子序列的长度并没有增加，但是出现了长度一样的情况，数量增加 count[i] += count[j] 。

2.1.4 返回结果

最终，将所有最长递增子序列的个数加在一起即为最终结果。

2.2 解答

from typing import List


class Solution:
    @classmethod
    def find_num_of_lis(cls, nums: List[int]) -> int:
        dp = [1] * len(nums)
        count = [1] * len(nums)
        max_length = 0
        num = 0
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        count[i] = count[j]
                    elif dp[j] + 1 == dp[i]:
                        count[i] += count[j]
        max_length = max(dp)
        for k in range(len(nums)):
            if dp[k] == max_length:
                num += count[k]
        return num


def main():
    # nums = [1, 3, 5, 4, 7]
    nums = [2, 2, 2, 2, 2]
    sln = Solution()
    print(sln.find_num_of_lis(nums))  # 5


if __name__ == '__main__':
    main()

执行用时： 876 ms , 在所有 Python3 提交中击败了 82.00% 的用户；
内存消耗： 15.1 MB , 在所有 Python3 提交中击败了 86.19% 的用户。

实际上，最后用于返回结果的代码可以进一步简化：

from typing import List


class Solution:
    @classmethod
    def find_num_of_lis(cls, nums: List[int]) -> int:
        dp = [1] * len(nums)
        count = [1] * len(nums)
        num = 0
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        count[i] = count[j]
                    elif dp[j] + 1 == dp[i]:
                        count[i] += count[j]
        max_length = max(dp)
        return sum(c for i, c in enumerate(count) if dp[i] == max_length)


def main():
    # nums = [1, 3, 5, 4, 7]
    nums = [2, 2, 2, 2, 2]
    sln = Solution()
    print(sln.find_num_of_lis(nums))  # 5


if __name__ == '__main__':
    main()