Mylocal train service最近添加了拨号通勤选项我正在尝试确定算法，以找到在给定日期的给定一组往返机票的最便宜组合。
这是英语中的问题给定一组天数和每天的乘车次数，以下哪种组合最便宜。
一张往返票，每趟费用为英镑。
一张7天车票，价格为X，连续7个日历日内无限制乘车。
一张30天的车票，在连续30个日历日内免费乘车。
连续365个日历日内无限制乘车的365天机票，价格为Z。
由于我很高兴将此限制为一次只能解决一年的问题，所以我认为天的列表可以很容易地存储在类似这样的数组中。
{0,0,1,1,1,0,0,2,1,0,0,0,4,0,1,1,...,0,1,1,5}
其中，数字等于每天往返的次数。
我可以使用什么算法来确定覆盖所有行程的最便宜的机票组合？
最佳答案
提示
您可以通过解决子问题来执行此操作：
What is the cheapest combination C[k] to cover all trips from day 0 up to day k?
为了计算这个子问题的答案，您可以简单地考虑购买一种票类型的每个情况通过从0开始解决问题并一直工作到365，您可以在解决子问题时使用以前的结果。
例如，假设在第100天你不需要旅行那么答案是C[99]，这是前几天最便宜的旅行方式。
然而，假设在第101天你需要做3次旅行那么C[101]的答案是最便宜的：
Buy round trip tickets today: cost 3*w+C[100]
Buy a 7 day ticket 7 days ago: cost x+C[101-7]
Buy a 30 day ticket 30 days ago: cost y+C[101-30]
当你计算出c[365]时，你可以将其与全年机票的成本z进行比较。
（如果在这个过程中，您发现自己要求i小于0时的成本c[i]，则c[i]的值为0。）