解題思路
動(dòng)態(tài)規(guī)劃：
定義 dp[i] 為考慮前 i 個(gè)元素漓踢，以第 i 個(gè)數(shù)字結(jié)尾的最長上升子序列的長度榴徐，注意 nums[i] 必須被選取技掏。在計(jì)算 dp[i] 之前署恍，我們已經(jīng)計(jì)算出了 dp[0……i-1] 的值。
設(shè) j∈[0,i)却妨，考慮每輪計(jì)算新 dp[i] 時(shí)饵逐，遍歷 [0,i) 列表區(qū)間，做以下判斷：
- 當(dāng) nums[i] > nums[j] 時(shí)： nums[i] 可以接在 nums[j] 之后（此題要求嚴(yán)格遞增）彪标，此情況下最長上升子序列長度為 dp[j] + 1梳毙；
- 當(dāng) nums[i] <= nums[j] 時(shí)： nums[i] 無法接在 nums[j] 之后，此情況上升子序列不成立捐下，跳過。
上述所有 1. 情況 下計(jì)算出的 dp[j] + 1的最大值萌业，為直到 i 的最長上升子序列長度（即 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)
初始狀態(tài)：dp[i]所有元素置 1婴程，含義是每個(gè)元素都至少可以單獨(dú)成為子序列，此時(shí)長度都為 1抱婉。
返回值：返回 dp 列表最大值档叔，即可得到全局最長上升子序列長度。
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(n^2)蒸绩，其中 n 為數(shù)組 nums 的長度衙四。動(dòng)態(tài)規(guī)劃的狀態(tài)數(shù)為 n，計(jì)算狀態(tài) dp[i]時(shí)患亿，需要 O(n) 的時(shí)間遍歷 dp[0…i?1] 的所有狀態(tài)传蹈，所以總時(shí)間復(fù)雜度為 O(n^2)。
空間復(fù)雜度：O(n)步藕，需要額外使用長度為 n 的 dp 數(shù)組惦界。
代碼
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
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)
