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

用户9613193

发布于 2026-06-16 20:01:08

700

动态规划—300. 最长递增子序列

前言
题目描述
基本思路
- 1. 问题定义
- 2. 理解问题和递推关系
- 3. 解决方法
- - 3.1 动态规划方法
  - 3.2 优化方法
- 4. 进一步优化
- 5. 小总结
代码实现
- Python
- - Python3代码实现
  - Python 代码解释
- C++
- - C++代码实现
  - C++ 代码解释
总结:

前言

在计算机科学中，动态规划是解决许多优化问题的强大工具。最长递增子序列问题是一个经典示例，它不仅展示了动态规划的基本思想，还引导我们思考如何优化算法。本文将详细探讨这一问题的基本思路及其实现方法，提供 Python 和 C++ 的解决方案，并对算法进行深入分析。

题目描述

基本思路

1. 问题定义

给定一个整数数组 nums，找出其中最长的递增子序列的长度。递增子序列是指从数组中选出的一个子序列，其中的元素按顺序排列并且毎个元素都大于前一个元素。

2. 理解问题和递推关系

该问题的目标是找到 nums 中的一个子序列，使得这个子序列的元素严格递增，且其长度最大。
- 定义
d p[i]
为以
nums[i]
结尾的最长递增子序列的长度。
- 对于每个元素
nums[i]
，我们可以通过查看它前面的所有元素
nums[j]
（j<i）
来更新
d p[i]
，如果
nums[j] < nums[i]
，那么可以将
nums[i]
加入到以
nums[j]
结尾的子序列中。因此，递推关系为：

d p[i]=\max (d p[i], d p[j]+1) \quad \text { for all } j<i \text { such that nums }[j]<\text { nums }[i]

3. 解决方法

3.1 动态规划方法

初始化一个数组 dp ，长度与 nums 相同，所有元素初始为 1 ，因为每个元素自身可以形成一个子序列。
双重矿环遍历数组 nums, 更新 dp 数组：
- 外层徎环遍历 i 从 1 到 n-1 （ n 为 nums 的长度）。
- 内层拰环遍历 j从 0 到 i-1, 更新 dp[i] 。
最终结果为 max(dp) ，即为最长递增子序列的长度。

3.2 优化方法

通过二分查找可以进一步将时间复杂度降低到

O(n \log n)

。

维护一个数组 tails，其中 tails[k] 存储当前长度为 k+1 的递增子序列的末尾元素的最小值。对于每个 num，可以使用二分育找确定它在 tails 中的位置，从而更新 tails。

4. 进一步优化

使用

O(n \log n)

的方法，可以用 bisect 库来实现高效的二分查找，优化子序列的构建过程。

5. 小总结

动态规划方法直观易懂，但其时间易杂度为

0\left(n^{\wedge} 2\right)

，适用于较小规模的问题。

通过优化算法，我们可以将时间复杂度降低到

O(n \log n)

，适用于更大规模的输入。

该问题是经典的动态规划问题，掌握这个问题对于解决相关的子序列问题非常有帮助。

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

代码实现

Python

Python3代码实现

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

        dp = [1] * len(nums)  # 初始化 dp 数组
        for i in range(1, len(nums)):  # 外层循环
            for j in range(i):  # 内层循环
                if nums[j] < nums[i]:  # 如果找到较小的元素
                    dp[i] = max(dp[i], dp[j] + 1)  # 更新 dp[i]

        return max(dp)  # 返回最长递增子序列的长度

Python 代码解释

初始化：创建 dp 向量，长度与 nums 相同，所有值为 1。
双重循环：外层循环遍历每个元素，内层循环检查所有之前的元素，更新 dp 数组。
返回结果：使用 max(dp) 获取最长递增子序列的长度。

C++

C++代码实现

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

        vector<int> dp(nums.size(), 1);  // 初始化 dp 数组
        for (int i = 1; i < nums.size(); i++) {  // 外层循环
            for (int j = 0; j < i; j++) {  // 内层循环
                if (nums[j] < nums[i]) {  // 如果找到较小的元素
                    dp[i] = max(dp[i], dp[j] + 1);  // 更新 dp[i]
                }
            }
        }

        return *max_element(dp.begin(), dp.end());  // 返回最长递增子序列的长度
    }
};