思路 日期变量型思路需要遍历一年中所有的天数，无论 days 的长度是多少。 但是观察日期变量型的递推式，我们可以看到，如果我们查询 dp(i)，而第 i 天我们又不需要出行的话，那么 dp 函数会一直向后计算 dp(i+1)=dp(i+2)=dp(i+3) 一直到一年结束或者有一天我们需要出行为止。那么我们其实可以直接跳过这些不需要出行的日期，直接找到下一个需要出行的日期。 算法 现在，我们令 dp(i) 表示能够完成从第 days[i] 天到最后的旅行计划的最小花费（注意，不再是第 i 天到最后的最小花费）。令 j1是满足 days[j1]>=...

思路和算法 我们用 dp(i) 来表示从第 i 天开始到一年的结束，我们需要花的钱。考虑到一张通行证可以让我们在「接下来」的若干天进行旅行，所以我们「从后往前」倒着进行动态规划。 对于一年中的任意一天： 如果这一天不是必须出行的日期，那我们可以贪心地选择不买。这是因为如果今天不用出行，那么也不必购买通行证，并且通行证越晚买越好。所以有 dp(i)=dp(i+1)； 如果这一天是必须出行的日期，我们可以选择买 1，7 或 30 天的通行证。若我们购买了 j 天的通行证，那么接下来的 j - 1 天，我们都不再需要购买通行证，只需要考虑第...