如何根据往返日期与日均乘车次数选择最优地铁订阅组合

可选票种清单 #

• 1次单程票
• 2次单程票
• 10次单程票
• 周末不限次票（覆盖周六、周日两天，无需连续）
• 1日不限次票
• 3日不限次票
• 周不限次票（覆盖周一至周日七天，无需连续）
• 月不限次票（覆盖当月1日至月末全时段）

以上票种均对应各自定价。

核心需求 #

给定具体的到达与离开日期，针对日均固定乘坐地铁次数n（n取值范围为1-8），找出成本最低的票种组合方案。

场景示例 #

• 当n=1时，若19日（周五）到达、23日（周四）离开，最优方案可选择1次单程票+周末不限次票+2次单程票（此为示例，未做实际成本核算）
• 当n=2时，可根据实际时段匹配对应高性价比票种组合

当前难点 #

目前仅找到针对1日、2日、7日票种的动态规划解法示例，但加入星期维度的票种（如周末票、周票）后，问题的状态转移逻辑变得复杂很多，难度大幅提升。

内容的提问来源于stack exchange，提问作者Valentin Bouis