理解LeetCode 983自底向上动态规划解法的困惑点

首先得明确dp数组的核心定义：dp[i]代表的是到第i天为止的最小旅行成本，不管第i天是不是旅行日——这是你困惑的关键，别把它局限在旅行日里。

为什么非旅行日的dp值可以直接用？ #

1. 非旅行日的dp值逻辑：如果第i天不在旅行列表days里，说明这天不需要旅行，自然不会产生额外成本，所以dp[i] = dp[i-1]——成本和前一天完全一样，一直延续到下一个旅行日。
2. 状态转移的本质：状态转移方程里的dp[day - k] + costs[k-1]（k=1,7,30），本质是在考虑「买一张k天票，覆盖从day - k + 1到day的所有天数」的成本方案：
   • 不管这k天里有没有旅行日，只要买了这张票，这段时间的所有旅行需求都被覆盖，不需要再花钱。
   • dp[day - k]是到day - k天的最小成本，加上k天票的价格，就是这个方案的总成本——哪怕day - k天不是旅行日，它的dp值已经是到那天的最低成本，完全可以作为这个方案的前置成本。

结合你的测试用例分析 #

测试用例：days = [1,2,3,4,41,42,43,44,45]，costs = [3, 500, 4]

• 第4到第40天都是非旅行日，所以dp[4] = dp[5] = ... = dp[40] = 4（因为买30天票覆盖前4天更划算）。
• 计算dp[41]时，dp[41-30] + costs[2] = dp[11] + 4，而dp[11]就是4（和dp[40]一样），所以这个方案的成本是8。同时还有dp[40]+3=7（买单日票）的方案，最终取最小值7。
• 这里用dp[11]完全没问题，因为它和dp[40]的成本一致，都是到对应天数的最小成本，代表「到第11天的成本+买一张30天票覆盖12-41天」的方案——虽然12-40天没旅行，但票的覆盖期包含这些天也不影响成本，只是这个方案不如单日票划算而已。

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