題目出處

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 控制搜尋範圍

Reference