帮忙看一下我 DP 的解法是不是有问题

根据第一问，需要先按照 deposit 降序排列，然后我的想法就是对于每个 ride，只有玩和不玩两种，所以 naive 的递归

def __solve(cost, deposit, amount, begin, end):
    if begin == end:
        return 1 if amount >= cost[begin] + deposit[begin] else 0
    else:
        result = __solve(cost, deposit, amount, begin + 1, end)
        if amount >= cost[begin] + deposit[begin]:
            result = max(result, 1 + __solve(cost, deposit, amount - cost[begin], begin + 1, end))
        return result

以此为基础的 DP

def max_ride(cost, deposit, amount):
    n = len(cost)
    opt = [[0 for _ in range(amount + 1)] for _ in range(n + 1)]
    for i in range(n-1, -1, -1):
        for j in range(1, amount + 1):
            opt[i][j] = opt[i+1][j]
            if j > cost[i] + deposit[i]:
                opt[i][j] = max(opt[i][j], 1 + opt[i+1][j-cost[i]])
    return opt

第四问就没有想到怎么实现 O(n^2)。初步只是发现如果 T 比所有的押金和费用和都大的话，所有项目都能玩。所以 T 大于一个值之后是没必要计算的