Bookings / VO 面试真题解析：Find Trip Costs Matching a Guest’s Budget 组合计费与预算匹配

Guests may want to visit multiple cities during one trip. Hotels in these cities offer various prices for the different days within the guest’s trip.

Your goal: find the cost of the trips that match the guest’s budget!

Input:

• The number of days the guest would like to stay at each city
• A budget (in EUR) the guest wants to spend at most for the entire trip
• A map containing the daily prices (in EUR) of the hotels in the cities the guest would like to visit during the trip

For the sake of simplicity, you can assume there is only one hotel per city in the input list, meaning all hotels in the list must be visited by the guest.

Output:

Sorted list (ascending) of prices for the trips matching the guest’s budget.

Example Input:

{
  "numberOfDaysPerCity": 2,
  "guestBudget": 309,
  "dailyPricePerCity": {"Paris": [10,40,5,80,10,50],
    "London": [60,30,20,70,50,70],
    "Amsterdam": [20,80,20,50,80,100]
  }
}

Example output:

[220,240,250,305]

Example trip that leads to a cost of 220:

• Day 1 and 2 in London costs 90 EUR
• Day 3 and 4 in Amsterdam costs 70 EUR
• Day 5 and 6 in Paris costs 60 EUR

这道题本质上是一个“多城市行程 + 预算约束”的组合枚举问题：给定每个城市需要停留的天数、总预算以及各城市每天的酒店价格，要求找出所有满足预算上限的行程总花费，并按升序返回。关键在于将每个城市在连续天数区间内的费用先计算出来，再通过回溯或 DFS 枚举城市访问顺序与分配方式，累加得到所有可能的总成本，最后筛出不超过预算的结果。示例中通过不同城市顺序组合，可以得到 220、240、250、305 等多个可行总价。