Python实现最长递增子序列：动态规划详解

最长递增子序列：动态规划详解

给定一个整数序列，找到其中最长严格递增子序列的长度。例如：

输入： 10 9 2 5 3 7 101 18 输出： 4

动态规划思路

使用动态规划解决此问题，我们定义 dp[i] 为以 nums[i] 结尾的最长递增子序列长度。那么我们可以得到递推关系：

dp[i] = max(dp[j] + 1)  其中 0 <= j < i 且 nums[j] < nums[i]

也就是说，对于每个 nums[i]，我们遍历之前所有比它小的 nums[j]，找到能够构成递增子序列的 dp[j]，并取最大值加 1 作为 dp[i] 的值。

动态规划表

以下为给定输入序列的动态规划表，其中每一列代表一个数字，每一行代表 dp[i] 的值：

| | 10 | 9 | 2 | 5 | 3 | 7 | 101 | 18 | | - | - | - | - | - | - | - | - | - | | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | 1 | 1 | 1 | 1 | 2 | 1 | 2 | 2 | 1 | | 2 | 1 | 1 | 1 | 2 | 1 | 3 | 3 | 1 | | 3 | 1 | 1 | 1 | 2 | 1 | 3 | 4 | 1 | | 4 | 1 | 1 | 1 | 2 | 1 | 3 | 4 | 1 | | 5 | 1 | 1 | 1 | 2 | 1 | 4 | 4 | 1 | | 6 | 1 | 1 | 1 | 2 | 1 | 4 | 5 | 1 | | 7 | 1 | 1 | 1 | 2 | 1 | 4 | 5 | 1 |

最终结果为 4，即最长递增子序列的长度。

Python 代码实现

def lengthOfLIS(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lengthOfLIS(nums))

代码解释

初始化 dp 列表，长度与输入序列相同，初始值均为 1，因为单个元素也是长度为 1 的递增子序列。
遍历输入序列，对于每个 nums[i]，遍历之前的元素 nums[j]，如果 nums[i] 大于 nums[j]，则更新 dp[i] 为 dp[j] 加 1 的最大值，即考虑包含 nums[j] 的递增子序列，并将其与不包含 nums[j] 的递增子序列长度进行比较，取最大值。
最后返回 dp 列表中的最大值，即最长递增子序列的长度。

总结

本文介绍了使用动态规划算法求解最长递增子序列问题，并提供了 Python 代码实现。通过动态规划表，可以清晰地理解算法的步骤，并有助于优化算法的实现。