983_最低票价.org

题目

思路

倒序遍历 dp

因为第 i 天的购票计划会受到未来日子中旅行计划的影响，所以倒序遍历

如果第 i 天没有出行计划，则花费的费用和第 i+1 天相同

code

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:

        if not days: return 0

        n = days[-1] + 30
        dp = [0] * (n + 1) # 旅行到第 i 天时，需要花费的总费用
        # 因为第 i 天的购票计划会受到未来日子中旅行计划的影响，所以倒序遍历
        for i in range(n - 30, -1, -1): 
            if i not in days: # 第 i 天没有旅行计划
                dp[i] = dp[i+1]
            else:
                dp[i] = min(
                    dp[i + 1] + costs[0],
                    dp[i + 7] + costs[1],
                    dp[i + 30] + costs[2]
                )
        # print('dp:', dp)
        return dp[0]