题解 | #神秘餐馆#

写了个python的dfs，一个树节点有m个子节点，但是准确率只有46%，求改正

prices = []
for _ in range(n):
    line = input().strip()  # 使用 strip() 移除字符串两端的空白字符
    prices.append(line)

price_int = [[0] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        char = prices[i][j]
        if char.isdigit():
            price_int[i][j] = int(char)
        elif char.isalpha():
            if char.isupper():
                price_int[i][j] = ord(char) - ord('A') + 10
            else:
                price_int[i][j] = ord(char) - ord('a') + 36

# 递归树有m个分支，每个分支递归完，返回下一层级的最大值，再和本层级的其它分支比大小
def dfs(day, budget_left, memory):
    if budget_left < 0 or day >= n:
        return day
    max_day = day            #m个个分支的最大值
    for i in range(m):
        if budget_left >= price_int[day][i]:
            next_day = day + 1
            next_budget = budget_left
            if day>=7 and next_day != 0:
                next_budget -= price_int[day][memory[day - 7]]
            else:
                next_budget -= price_int[day][i]
            memory.append(i)
            current_day = dfs(next_day, next_budget, memory)
            max_day = max(max_day, current_day)
            memory.pop()         # 回溯，防止其它分支的输入被篡改
    return max_day

memory = []
max_days = dfs(0, budget, memory)
print(max_days)