pdd算法题题目--吃汉堡

pdd算法题题目：未来N天，多多君想好了要吃的汉堡，且已知第天,的汉堡价格为Pi，吃掉汉堡后可以获得,与价格同等数量的汉堡积分。每100个汉堡积分会,自动兑换成一张免单券，可以免费吃任意汉堡,免单券的有效期为3天，且使用免单券吃掉的汉堡不能获得汉堡积分。找到一个最省钱的吃汉堡计划

同学问我此题如何写，我们都不会尝试了半天后，写了回溯和动态规划两种方式，不知道是不是能通过所有案例，试了一些发现是对的代码如下：

def dfs(nums, path, ans, curMon, start):

    if start == len(nums):
        if sum(path) > ans[0]:
            ans[0] = sum(path)
        return
    if curMon >= 100:
        curMon -= 100
        for i in range(3):
            if start+i < len(nums):
                path.append(nums[start+i])
                dfs(nums, path, ans, curMon, start+i+1)
                path.pop()
                curMon += nums[start+i]
    else:
        curMon += nums[start]
        dfs(nums, path, ans, curMon, start+1)


def min_cost_to_eat_hamburgers(N, prices):
    MAX = sum(prices)
    dp = [[MAX] * (MAX + 1) for _ in range(N+1)]   # dp[i][j]表示第i天结束时，积分为j的最小花费
    dp[0][0] = 0  # 第0天，0积分的花费为0

    for i in range(1, N+1):
        price = prices[i-1]
        for j in range(1, MAX+1):
            # 不使用免单券的情况
            if j >= price:
                dp[i][j] = min(dp[i][j], dp[i-1][j-price] + price)
            # 使用免单券的情况
            if j >= 100:
                if i+1 < N+1:dp[i+1][j-100] = min(dp[i+1][j-100], dp[i][j])
                if i+2 < N+1:dp[i+2][j-100+prices[i]] = min(dp[i+2][j-100+prices[i]], dp[i][j]+prices[i])
                # if i+3 < N+1:dp[i+2][j-100+prices[i]] = min(0, 1)
                if i+3 < N+1 and j-100+prices[i]+prices[i+1] <=MAX:dp[i+3][j-100+prices[i]+prices[i+1]] = min(dp[i+3][j-100+prices[i]+prices[i+1]], dp[i][j]+prices[i]+prices[i+1])       

    return min(dp[-1])

nums = [70, 60, 20, 80, 50, 30, 40, 70]
ans = [0]
dfs(nums, [], ans, 0, 0)
print(sum(nums)-ans[0])
print(min_cost_to_eat_hamburgers(len(nums), nums))