说一说最长子序列(初稿)

leetcode300 原题。

思路：
求最优解的问题，可以转化为动态规划问题，动态规划问题先要找到子问题。
子问题是什么？
由于数组本身的顺序是不可以改变的。而最长子序列必然是以某一个数结尾的。所以不妨将nums(i)结尾的最长子序列求出来，直到把最后一个位置结尾的最长子序列求出来，
再从dp中找到最大的数，这便是整个数组的最长子序列。
何求dp(i)?
dp(i)就是以nums(i)为结尾的最长子序列长度。要求最长子序列长度，先求所有子序列长度，然后再取最大的。
定义 dp[i]为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度，注意 nums[i] 必须被选取。

假如所有的j都比i大呢？ 那dp(i)只能是1。dp数组初始的时候，都是1，因为最坏的情况是数组是倒序的，a(i+1)总比ai小的时候，以ai结尾的最长子序列只能为1

接着求状态转移方程：
dp[i]=max(dp[i],dp[j]+1)
只要nums(j) < nums(i),就能够拼接，此时求得的是子序列，并不是最长子序列，最长子序列需要比较得出。

以第i个位置作为结尾的数字的最长子序列。 不仅要以a(i)为结尾,而且子序列还要最长。
以i为结尾的数字和左边的数字比较，如果numsj > numsi, 则j和i无法拼接为子序列，所以，此时dpi就是1，i要和前面所有的j比较
一旦numsj < numsi，便意味着j可以和i拼接成子序列。则dpi = dpj + 1, 子序列长度增长了1. 所以，从a0至ai-1的每一个数和ai相比，都会产生一个dpi, 在这些dpi中
找到最大值，就是最长子序列。

for i in range(size):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[j + 1],dp[i])
    
return max(dp)

完整的代码是：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        size = len(nums)

        dp = [1]*size
        if size <=  1:
            return size
        for i in range(1,size):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i],dp[j]+1)

        return max(dp)

ps:以前我以为所有的dp问题只要求最后一个即可。但是这一题，求的dp最后一个并不是最长子序列。原因在于本题的dp的意思是，
以第i个位置的数字‘结尾‘的最长子序列，原数组的最长子序列一定是以某个数字结尾的，且它一定是由它之前的以某一个数字结尾的最长子序列+1得到的。如果设置的是范围到了i的最长子序列，则dp的最后一个便是最长子序列了。

本题还有什么其他的方法能够优化解呢？
思考另一个动态规划问题——编辑距离。

说一说最长子序列(初稿)

原文：https://www.cnblogs.com/goto2091/p/13723302.html