[动态规划]Leetcode 300.最长上升子序列(python)

如果读者对于动态规划思路解法还不是很了解，可以先点击链接查阅我之前的一篇博文《算法之【动态规划】详解》，很详细的介绍了动态规划求解思路及方法，有利于你更好的学习动态规划。

题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例1

输入: [10,9,2,5,3,7,101,18]

输出: 4

解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

DP定义及状态方程

定义dp[i]表示以第i个元素结尾的最长递增子序列长度。那么对于该元素前面的i-1个元素中如果有元素j比nums[i]小，那么dp[i]就等于以元素j结尾的最长递增子序列长度加1，即dp[i] = max(dp[i], dp[j] + 1);遍历i前面的所有元素，只要满足元素j比元素i小，则计算一次dp[i] = max(dp[i], dp[j] + 1)，遍历完成后即可求得dp[i]的最大值，即以第i个元素结尾的最长递增子序列长度。

此题目的最终答案即为dp数组中的最大值：max(dp)

初始边界条件

以每个元素为结尾的最长递增子序列长度一定包含本身，因此最小都是1，所以初始条件是以每个元素为结尾的最长递增子序列长度均为1。

初始边界条件：dp = [1 for _ in range(n)]，n为数组长度。

最终代码

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0   
        n = len(nums)
        # # dp[i]表示以第i个元素结尾的最长递增子序列长度,初始值为1
        dp = [1 for _ in range(n)]
        # 遍历每一个元素，求以每一个元素为结尾的最长递增子序列长度
        for i in range(n):
            for j in range(i):
                # 遍历i前面的所有元素，如果nums[j] < nums[i]，则求一次dp[i] = max(dp[i],dp[j] + 1)
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i],dp[j] + 1)
        return max(dp)