第一章：动态规划设计：最长递增子序列

labuladong动态规划设计：最长递增子序列

300. 最长上升子序列

• dp数组的含义：以nums[i] 结尾的当前最长上升子序列的长度记录在dp[i]中
• 状态转移方程：nums[i] 与它之前的元素nums[j]进行比较，若大于nums[j], 则比较之前保存的dp[i] 和dp[j]+1 的大小，并更新dp[i] （始终保存最大值）
• base case： 上升子序列至少为自己，因此dp数组初始化为1

如何找到动态规划的状态转移关系：

1、明确 dp 数组的定义。这一步对于任何动态规划问题都很重要，如果不得当或者不够清晰，会阻碍之后的步骤。

2、根据 dp 数组的定义，运用数学归纳法的思想，假设 dp[0…i-1] 都已知，想办法求出 dp[i]，一旦这一步完成，整个题目基本就解决了。

但如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组。

class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        dp=[1 for _ in range(len(nums))]
        for i in range(1,len(nums)):
            for j in range(i):
                if nums[i]>nums[j]:
                    dp[i]=max(dp[i],dp[j]+1)
        return max(dp)