題目
BM71 最長上升子序列(一)
分析
dp[i] 考慮到下標i，其組成的最長上升子序列長度
可以用動態規劃的原因： 到i的結果可以由到j （j<i) 的結果推出，只需要判斷下標j對應的數字是否比下標i 對應的字母小即可
注意：要特判數組為空的情況
狀態轉移：dp[i] = max(dp[j] + 1,dp[i])
代碼
class Solution:def LIS(self , arr: List[int]) -> int:# write code heren = len(arr)# 特判數組為空的情況 0<=nif n == 0:return 0# dp[i] 考慮到下表為i的數組，其最長上升子序列長度，初始化為1，至少有一個字母dp = [1 for i in range(n)]# 考慮到下標為ifor i in range(n):# 考慮i前面的升序元素for j in range(i):if arr[j]<arr[i]:dp[i] = max(dp[j] + 1,dp[i])return max(dp)
)
)
