509. Fibonacci Number

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # dp[i]: longest subsequence length ending with nums[i]
        # time O(N^2) space O(N)
        # base case 
        dp = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i],dp[j] + 1)
        # get biggest val in dp[]
        res = 0
        for i in range(len(dp)):
            res = max(res,dp[i])
        return res # return max(dp)