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

[letianqiu]

根据第一问，需要先按照 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 大于一个值之后是没必要计算的

[geelaw]

状态 (a, b) 表示前 a 个项目玩了 b 个。令 f(a, b) = 开始需要持有的钱的最小值

要在前 a 个项目玩 b 个，你可以选择玩第 a 个或者不玩第 a 个

f(a, b) = min { f(a - 1, b), max { f(a - 1, b - 1), D[a] } + C[a] }

最后寻找 argmax(m) { f(n, m) <= T }

[letianqiu]

@geelaw 初始化的时候 f(a, b)是不是应该设为-1，开始之前并不知道最少要花多少钱。另外就是想请问一下你是如何思考得出保存的状态应该是最少需要花多少钱的。现在看来这题和 UVA 10154 的乌龟塔类似，都是需要排序之后保存最少达成 k 需要的 resource，而不是保存最大的 k。另外就是哪些情况下，DP 之前需要对原始的数据排序。

[geelaw]

@letianqiu

只需要知道 f(a,0)=0, f(a,a+1)=+infty 然后按照顺序填表即可。

因为题目要求 n^2 的算法，所以状态数最多 n^2，要用到钱数限制很容易想到，这个题做多了就会了

这个 n^2 的算法不需要排序，“排序”是没有普遍定义的（很难说“对数据排序”是一个 universally applicable 的操作），根据解决问题的不同有不同的处理。

[geelaw]

另，如果这是你的作业题（或者任何需要你书写报告或代码上交的），你应该给予我 acknowledgement

[letianqiu]

@geelaw 我又想了一下，不知道是不是我的理解有误，感觉状态方程有问题。“开始需要持有的钱的最小值”这个是不是表示如果前 a 个项目玩 b 个(a>=b)，最少需要多少钱。按这样理解，当玩第 a 个的时候，a-1 个项目玩了 b-1 个以后，剩下的钱至少要大于等于 cost[a]+deposit[b]，才能玩 a。问题是并不知道 f(a-1, b-1)最后剩余多少钱，也许剩余的钱已经大于等于 deposit[a] + cost[a]了。比如 cost=[1, 1], deposit=[10, 1]的情况。同样有可能发生剩余的钱不够 deposit[a]，但是 f(a-1, b-1) > deposit[a]。比如 cost=[3, 1], deposit=[2, 3]

[geelaw]

@letianqiu 是那个意思。懒得思考，那就先把项目按照押金递减排序吧，这样转移方程就是正确的了。考虑玩第 a 项且前 a-1 项玩了 b-1 项的情况，这样玩：先玩第 a 项，退完押金再玩前 a-1 项里的 b-1 项。