300.最长上升子序列（动态规划）

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

总结一下本题与279.完全平方数中的的动态规划用法：

　　拿dp[ 10 ]的推演途径来举例

　　279：  从 10 - 1，10 - 4，10 - 9 中取最大值

　　　　dp[ 10 ] = dp[ 9 ] + 1

　　　　dp[ 10 ] = dp[ 6 ] + 1

　　　　dp[ 10 ] = dp[ 1 ] + 1

　　300：if nums[ 10 ] > nums[ i ] ：从 1 2 3 4 5 6 7 8 9 中取其最大值

　　　　dp[ 10 ] = max( dp[ 10 ] ,  dp[ i ] + 1)

以上两题都是从小推到大（1-10），每一步都要遍历完所有的可能性，而不是从大往小（从10 往 1 4 9）推

class Solution:

    def lengthOfLIS(self, nums: List[int]) -> int:

        if not nums: return 0

        dp = [1 for i 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)