前端开发者的Yandex.Blitz竞赛最近结束了，我想分析一个问题。（我再次重申，比赛已经结束）。在我看来，这个问题介于背包问题和用线段覆盖一组点之间。这是它的完整措辞：

有一个 devops Petya。在工作中，他需要在接下来的 100 天内在某些日子值班。彼佳乘地铁上班。订阅票被引入地铁，从第一次乘坐之日起的一定天数内有效。门票的持续时间越长，每天的费用就越低。我们需要帮助 Petya 省钱，并在考虑到他的值班时间的情况下，提前三个月计算出他需要购买哪些票，以使他们的总成本尽可能低。彼佳也不喜欢随身携带很多票，如果有几种最低成本相同的票，那么彼佳需要一张票少的。如果有多个这样的选项（最低成本和门票数量相同），那么其中任何一个都适合 Petya。getCheapestTickets(days, tickets)，它将 Petya 的值班表 ( days) 和可能的订阅票选项 ( tickets) 作为输入，并作为输出给出 Petya 需要购买的票列表（以票选项输入数组中的索引的形式）。Petya 的值班时间表以排序后的数字数组形式给出（从 1 到 100 包括在内），每个数字表示值班日的序号：

// Петя должен дежурить на второй, пятый, десятый и сорок пятый день относительно текущей даты  
[2, 5, 10, 45]

每个订阅票由以下接口描述：

interface Ticket {  
    // количество дней, в течение которых билет действует со дня первой поездки по нему,  
    // включая этот день (от 1 до 100 включительно)  
    duration: number;  
    // стоимость билета (от 1 до 100 включительно)  
    cost: number;  
}

门票选择数量不超过10个，并保证所有门票价格不同，门票有效期越多，一日成本越低。

输入格式

days:
[1, 2, 4, 6, 7, 8, 9, 10, 20]
tickets:

[  
    { cost: 3, duration: 1 },  
    { cost: 10, duration: 7 },  
    { cost: 20, duration: 30 }  
]

输出格式

[0, 0, 1, 0]

我的问题是我的解决方案没有及时通过。首先，我尝试通过递归遍历整个决策树（JavaScript）来解决这个问题：

const getCheapestTickets = (days, tickets) => {
  // Вспомогательная функция для обхода всех вариантов билетов.
  // l указывает на текущий день из массива days.
  const wrapper = (l) => {
    let min = null;

    // Обходим все билеты.
    for (let i = 0; i < tickets.length; i += 1) {
      const ticket = tickets[i];
      let j = l;

      // Считаем количество дней, которые покрывает данный билет.
      const skip = days[l] + ticket.duration;
      while (skip > days[j]) {
        j += 1;
      }

      let curr;
      if (j < days.length) {
        // Рекурсивно ищем решение для оставшихся дней.
        curr = wrapper(j);
        curr.sum += ticket.cost;
      } else {
        curr = { sum: ticket.cost, includes: [] };
      }

      const currIncludes = [i, ...curr.includes];
      curr = { ...curr, includes: currIncludes };

      if (min === null) {
        min = curr;
      } else if (
        (curr.sum === min.sum && curr.includes.length < min.includes.length)
        || curr.sum < min.sum) {
        min = curr;
      }
    }

    return min;
  };

  return wrapper(0, 0).includes;
};

在这里，我不明白如何丢弃决策分支。我看不出如何将其简化为经典的背包问题，通过矩阵寻求解决方案。接下来，我尝试编写相同的解决方案，但没有递归，也绕过所有可能的变化，但在树的帮助下。也没有及时过去。请帮助制定更优化的算法。解决方案是单线程的，这一点很重要。