leetcode300 原题。
思路：
求最优解的问题，可以转化为动态规划问题，动态规划问题先要找到子问题。
子问题是什么？
要找最长上升子序列，先找子序列，再从中找到最大的。分为子问题就是，只要找到每个位置的最大子序列，那么在其中找到最大的值，就是整个数组的最大上升子序列。
每个位置的最大上升子序列要怎么求？每个位置可以有许多上升子序列，从中找到最大的，就是该位置的最大上升子序列。
关键是找到所有以ai结尾的上升子序列，然后比较其长度，找到最大的，则dpi就是ai的最大上升子序列。
动态规划的思路就是先找到子问题，然后分析子问题的思路可以用于解决总问题。
假设有一个数字串 34198，求它的最大上升子序列，请问，如何分析？
以3结尾的上升子序列有哪些？ 只有它自身，那么最长子序列dp1 = 1
以4结尾的上升子序列有哪些？ ，34，4， 所以有2个上升子序列，其中最长的是34，长为2，dp2 = dp1 + 1,
以1结尾的呢？ 只有它自身， 因为3，4都比1要大 dp3 = 1
以9结尾的呢， 3比9小，可以组成上升子序列， 4比9小，可以组成上升子序列，1比9小可以组成上升子序列。故39，49，19，349.最长的上升子序列是349，长度为3
349是34和9的拼接，即dp2+1,得到了dp4, 更具体低讲，dp(i+1)不一定是dpi得到的，也可能是dp(i-k)得到的。
以9结尾的，不断和前面的数进行比较，如果比前面的大，则说明可以拼接，则此时拼接出来的上升子序列长度为dpj + 1, 把所有的dpj + 1比较 得到最大的值，就是 dpi
(从中可以发现，dpi不是以前理解的那样，非得一次从dp(i-1)中得到，也可能是经过多次比较得到)。
由于数组本身的顺序是不可以改变的。而最长子序列必然是以某一个数结尾的。所以不妨先将以nums(i)结尾的最长子序列求出来，直到把最后一个位置结尾的最长子序列求出来，
再从dp中找到最大的数，这便是整个数组的最长子序列。要求numsi的最长子序列，先把numsi的所有子序列求出来，然后比较得到最大值。
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的最后一个便是最长子序列了。 dp的答案不一定是最后一个dp，也可能是在dp中找到最大的。这和dp的定义有关。
本题还有什么其他的方法能够优化解呢？
思考另一个动态规划问题——编辑距离。
原文创作：goto2091
原文链接：https://www.cnblogs.com/goto2091/p/13723302.html
