动态规划是解决算法问题的强大工具之一，其中最长递增子序列（Longest Increasing Subsequence，LIS）是一个经典的动态规划问题。本文将介绍 LIS 的基本概念、解题思路以及相关实现。

概念介绍

最长递增子序列指的是在一个序列中，找到一个子序列，该子序列的元素按顺序排列，且长度最长。例如，给定序列 [10, 9, 2, 5, 3, 7, 101, 18]，其最长递增子序列为 [2, 3, 7, 101]。

解题思路

LIS 问题的核心在于如何有效地计算子序列的长度。以下是一种常见的解决思路：

  1. 定义状态：设 dp[i] 表示以序列中第 i 个元素结尾的最长递增子序列的长度。
  2. 状态转移：对于每个元素 nums[i]，遍历所有小于 i 的元素 nums[j]，如果 nums[j] < nums[i]，则 dp[i] 可能由 dp[j] 转移而来，即 dp[i] = max(dp[i], dp[j] + 1)。
  3. 计算结果：遍历所有 dp[i]，找到最大的值即为最长递增子序列的长度。

Python 代码实现

def lengthOfLIS(nums):
    if not nums:
        return 0
    
    dp = [1] * len(nums)
    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)
    return max(dp)

# 示例
print(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))  # 输出：4

扩展阅读

想要深入了解动态规划以及 LIS 的更多实现方式，可以阅读以下文章：

Dynamic Programming

注意：本文内容仅供学习和交流，请勿用于非法用途。