【LeetCode】动态规划—673. 最长递增子序列的个数（附完整Python/C++代码）

前言

在算法研究中，序列问题是一个常见而重要的主题。最长递增子序列问题不仅在理论上具有挑战性，同时在许多实际应用中也非常有用，如数据分析、动态规划和计算机视觉等领域。本文将深入探讨如何利用动态规划和计数技巧来解决该问题，同时提供 Python 和 C++ 的具体实现，以帮助读者更好地理解和掌握这一算法。

题目描述

基本思路

1. 问题定义

给定一个整数数组 nums，我们需要找到其中最长的递增子序列的长度，以及该长度的递增子序列的个数。

2. 理解问题和递推关系

• 最长递增子序列（LIS）是指在数组中选择若干元素，使得它们的顺序与原数组相同，且毎个元素都大于前一个元素。

・ 定义 dp[i] 为以 nums[i] 结尾的最长递增子序列的长度, count[i] 为以 nums[i] 结尾的最长递增子序列的个数。

・递推关采如下：
・对于每个 nums[i]，音看其前面的所有元素 nums[j]（ j < i ）：

• 如果 nums[j] < nums[i], 则更新 dp[i] :

$$dp[i]=\max (dp[i],dp[j]+1)$$

• 更新 count[i]:
• 如果 $dp[j]+1>dp[i]$ ，说明找到了一个更长的递增子序列，更新 count[i] 为 count[j]。
• 如果 $dp[j]+1==dp[i]$ ，说明找到了一个同样长度的递增子序列，累加 count[j] 到 count[i]。

3. 解决方法

3.1 动态规划方法

1. 初始化两个数组 $dp$ 和 count, 长度与 nums 相同:
   • dp[i] 初始化为 1，因为每个元素本身可以形成长度为 1 的递增子序列。
   • count[i]初始化为 1 ，因为毎个元素自身的子序列个数为 1 。
2. 使用双重矿环遍历数组 nums，更新 dp[i] 和 count[i]数组。
3. 最终，找到 $\max (\mathrm{dp})$ 来获取最长递增子序列的长度，并对 count 数组进行遍历，累加所有 count[i] (当 dp[i] 等于最长长度) 以获得该长度子序列的个数。

3.2 优化方法

• 使用二分查找技术可以进一步优化 $dp$ 数组的构建，使时间复杂度降低到 $O(n\log n)$ 。

• 通过维护一个数组 tails 来记录当前长度的递增子序列的末尾元素，从而更新 count。

4. 进一步优化

• 利用 bisect 库可以方便地在 tails 中找到合适的位置，并更新计数，进一步提高效率。

5. 小总结

• 本文通过动态规划方法有效解决了计算最长递增子序列及其个数的问题。
• 该问题展示了动态规划与计数相结合的技巧，适用于类似的序列问题。

以上就是最长递增子序列的个数问题的基本思路。

代码实现

Python

Python3代码实现

class Solution:
    def findNumberOfLIS(self, nums):
        if not nums:
            return 0

        n = len(nums)
        dp = [1] * n  # 初始化 dp 数组
        count = [1] * n  # 初始化 count 数组

        for i in range(n):  # 遍历每个元素
            for j in range(i):  # 检查前面的元素
                if nums[j] < nums[i]:  # 如果找到较小的元素
                    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(count[i] for i in range(n) if dp[i] == max_length)  # 返回该长度的个数

Python 代码解释

• 初始化：创建 dp 和 count 数组，分别存储最长递增子序列的长度和个数。
• 双重循环：外层循环遍历每个元素，内层循环检查之前的元素，更新 dp 和 count 数组。
• 返回结果：找到 max(dp)，然后累加所有 count[i]（当 dp[i] 等于最大长度）以获得结果。

C++

C++代码实现

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;

        int n = nums.size();
        vector<int> dp(n, 1);  // dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度
        vector<int> count(n, 1);  // count[i] 表示以 nums[i] 结尾的最长上升子序列的个数
        int max_length = 0;  // 记录最长上升子序列的长度
        int max_count = 0;   // 记录最长上升子序列的个数

        // 动态规划计算 dp 和 count 数组
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;  // 更新长度
                        count[i] = count[j]; // 更新个数
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j]; // 追加个数
                    }
                }
            }
            max_length = max(max_length, dp[i]); // 更新最大长度
        }

        // 计算最长上升子序列的总个数
        for (int i = 0; i < n; ++i) {
            if (dp[i] == max_length) {
                max_count += count[i]; // 统计个数
            }
        }

        return max_count; // 返回结果
    }
};

C++ 代码解释

1. 初始化：

• dp[i] 用于存储以 nums[i] 结尾的最长上升子序列的长度。
• count[i] 用于存储以 nums[i] 结尾的最长上升子序列的个数。
• max_length 和 max_count 分别用于记录最长上升子序列的长度和个数。

2. 动态规划过程：

• 外层循环遍历每个元素 i，内层循环遍历 i 之前的所有元素 j。
• 如果 nums[i] 大于 nums[j]，检查是否形成了更长的上升子序列。
• 如果找到了更长的序列，更新 dp[i] 和 count[i]；如果找到了相同长度的序列，增加 count[i]。

3. 计算结果：

• 遍历 dp 数组，统计最长上升子序列的总个数。

总结:

• 本文通过对最长递增子序列及其个数问题的深入分析，展示了动态规划的强大能力。
• 结合计数的技巧，使得解决方案不仅有效且易于理解，适合解决类似的复杂问题。