題目描述
給定一個(gè)無序的整數(shù)數(shù)組，找到其中最長(zhǎng)上升子序列的長(zhǎng)度早敬。
示例
示例 1：
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長(zhǎng)的上升子序列是 [2,3,7,101]天梧，它的長(zhǎng)度是 4。
說明
- 可能會(huì)有多種最長(zhǎng)上升子序列的組合，你只需要輸出對(duì)應(yīng)的長(zhǎng)度即可。
- 你算法的時(shí)間復(fù)雜度應(yīng)該為 O(n2) 鞍匾。
解答方法
方法一：動(dòng)態(tài)規(guī)劃
思路
狀態(tài)定義：
dp[i]的值代表 nums 前 i個(gè)數(shù)字的最長(zhǎng)子序列長(zhǎng)度。
轉(zhuǎn)移方程： 設(shè) j∈[0,i)骑科，考慮每輪計(jì)算新 dp[i]時(shí)橡淑，遍歷 [0,i)列表區(qū)間，做以下判斷：
- 當(dāng) nums[i] > nums[j]時(shí)：nums[i] 可以接在 nums[j] 之后（此題要求嚴(yán)格遞增）纵散，此情況下最長(zhǎng)上升子序列長(zhǎng)度為 dp[j] + 1梳码；
- 此情況 下計(jì)算出的dp[j]+1 的最大值，為直到 i 的最長(zhǎng)上升子序列長(zhǎng)度（即dp[i] ）伍掀。實(shí)現(xiàn)方式為遍歷 j時(shí)掰茶，每輪執(zhí)行 dp[i] = max(dp[i], dp[j] + 1)。轉(zhuǎn)移方程： dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)蜜笤。
- 當(dāng) nums[i] <= nums[j]時(shí)： nums[i]nums[i] 無法接在 nums[j]之后濒蒋，此情況上升子序列不成立，跳過把兔。
轉(zhuǎn)移方程： dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)沪伙。
初始狀態(tài)：
dp[i]dp[i] 所有元素置 11，含義是每個(gè)元素都至少可以單獨(dú)成為子序列县好，此時(shí)長(zhǎng)度都為 11围橡。
返回值：
返回 dpdp 列表最大值，即可得到全局最長(zhǎng)上升子序列長(zhǎng)度缕贡。
代碼
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if len(nums)==0:
return 0
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
時(shí)間復(fù)雜度
O(n^2),遍歷計(jì)算 dpdp 列表需 O(N)O(N)翁授，計(jì)算每個(gè) dp[i]dp[i] 需 O(N)O(N)。
空間復(fù)雜度
O(N),dp列表占用線性大小額外空間晾咪。
