題目出處
300. Longest Increasing Subsequence
難度
Medium
個人範例程式碼
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# 1 3 5 4 7
# 1 1 1 1 1
# 1 2 3 3 4
dp = [1 for _ in range(len(nums))]
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j]+1)
return max(dp)
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
經典題目 LIS，使用 DP 解題
# 1 3 5 4 7
# 1 1 1 1 1
# 1 2 3 3 4
- init: dp 都 1
- function: dp[i] = max(dp[i], dp[j]+1) if 0 <= j < i
- ans: max(dp)
input handling
同 DP 內控制範圍
Boundary conditions
用 for loop 控制搜尋範圍