def fib(n):
    """
    计算斐波那契数列的第n个数
    时间复杂度：O(n)
    空间复杂度：O(n)
    """
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

def lengthOfLIS(nums):
    """
    计算最长递增子序列的长度
    时间复杂度：O(n^2)
    空间复杂度：O(n)
    """
    if not nums:
        return 0
    
    dp = [1] * len(nums)
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

def knapsack(weights, values, capacity):
    """
    0-1背包问题
    weights: 物品重量列表
    values: 物品价值列表
    capacity: 背包容量
    返回：最大价值
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], 
                              dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]