如果读者对于动态规划思路解法还不是很了解，可以先点击链接查阅我之前的一篇博文《算法之【动态规划】详解》，很详细的介绍了动态规划求解思路及方法，有利于你更好的学习动态规划。
题目描述
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例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)
如果喜欢作者，欢迎点赞、收藏及关注，谢谢！
