如果讀者對于動態(tài)規(guī)劃思路解法還不是很了解，可以先點擊鏈接查閱我之前的一篇博文《算法之【動態(tài)規(guī)劃】詳解》就斤，很詳細(xì)的介紹了動態(tài)規(guī)劃求解思路及方法控嗜，有利于你更好的學(xué)習(xí)動態(tài)規(guī)劃。
題目描述
給定一個無序的整數(shù)數(shù)組蒜茴，找到其中最長上升子序列的長度星爪。
示例1
輸入: [10,9,2,5,3,7,101,18] 輸出: 4 解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4粉私。
DP定義及狀態(tài)方程
定義dp[i]表示以第i個元素結(jié)尾的最長遞增子序列長度顽腾。那么對于該元素前面的i-1個元素中如果有元素j比nums[i]小，那么dp[i]就等于以元素j結(jié)尾的最長遞增子序列長度加1诺核，即dp[i] = max(dp[i], dp[j] + 1);遍歷i前面的所有元素抄肖，只要滿足元素j比元素i小，則計算一次dp[i] = max(dp[i], dp[j] + 1)窖杀，遍歷完成后即可求得dp[i]的最大值漓摩，即以第i個元素結(jié)尾的最長遞增子序列長度。
此題目的最終答案即為dp數(shù)組中的最大值：max(dp)
初始邊界條件
以每個元素為結(jié)尾的最長遞增子序列長度一定包含本身入客，因此最小都是1管毙，所以初始條件是以每個元素為結(jié)尾的最長遞增子序列長度均為1腿椎。
初始邊界條件：dp = [1 for _ in range(n)]，n為數(shù)組長度夭咬。
最終代碼
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
# # dp[i]表示以第i個元素結(jié)尾的最長遞增子序列長度,初始值為1
dp = [1 for _ in range(n)]
# 遍歷每一個元素酥诽，求以每一個元素為結(jié)尾的最長遞增子序列長度
for i in range(n):
for j in range(i):
# 遍歷i前面的所有元素，如果nums[j] < nums[i]皱埠，則求一次dp[i] = max(dp[i],dp[j] + 1)
if nums[i] > nums[j]:
dp[i] = max(dp[i],dp[j] + 1)
return max(dp)
如果喜歡作者肮帐，歡迎點贊、收藏及關(guān)注边器，謝謝训枢！
