題目

給你一個整數(shù)數(shù)組 nums ，找到其中最長嚴格遞增子序列的長度。子序列是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列。

例：
輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 。

方法：動態(tài)規(guī)劃

• 若整數(shù)數(shù)組 nums 的長度為 1，那么最長遞增子序列即為該數(shù)字，長度為 1
• 同理，由于 dp[i] 表示 i 及 i 以前的組成的數(shù)組所擁有的最長遞增子序列的長度，那么應(yīng)將其初始化為 1 而非之前的 0
• result 表示此時（最終）的最長遞增子序列的長度
• 外層循環(huán)即為對除第一個數(shù)字外的其他數(shù)字 i 從前到后的循環(huán)，而內(nèi)層循環(huán)為對從第一個數(shù)字到 i-1 數(shù)字的循環(huán)。
  • 若數(shù)字 nums[i] 大于此時的 nums[j]，及表示此時的數(shù)字 nums[i] 可以同 nums[j] 和與 nums[j] 組成最長遞增序列的數(shù)字序列結(jié)合組成新的遞增序列。通過對每個遞增序列的長度進行對比，選擇最長遞增子序列，即得到 dp[i]
  • 每結(jié)束一次內(nèi)層循環(huán)，計算一次此時的最長遞增子序列的長度 result

class Solution(object):
    def lengthOfLIS(self, nums):
        if len(nums) == 1:
            return 1
        dp = [1] * len(nums)
        result = 0
        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)
            result = max(result, dp[i])
        return result

參考

代碼相關(guān)：https://programmercarl.com/0300.%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97.html