LeetCode 983. 最低票价

Categories:

题目描述
思路分析
1. 解法一：按天 DP（推荐）
相似题目

题目描述

✅ 983. 最低票价

思路分析

解法一：按天 DP（推荐）

核心思路：

用集合标记需要出行的日期。

dp[i] 表示覆盖到第 i 天的最低成本。

若第 i 天不出行：dp[i] = dp[i-1]。

若出行：

dp[i] = min(dp[i-1] + cost1, dp[i-7] + cost7, dp[i-30] + cost30)。

复杂度分析：

时间复杂度：O(D)，其中 D 为最后一天日期。

空间复杂度：O(D)。

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        Set<Integer> travel = new HashSet<>();
        int lastDay = 0;
        for (int d : days) {
            travel.add(d);
            lastDay = Math.max(lastDay, d);
        }

        int[] dp = new int[lastDay + 1];
        for (int i = 1; i <= lastDay; i++) {
            if (!travel.contains(i)) {
                dp[i] = dp[i - 1];
                continue;
            }

            int c1 = dp[Math.max(0, i - 1)] + costs[0];
            int c7 = dp[Math.max(0, i - 7)] + costs[1];
            int c30 = dp[Math.max(0, i - 30)] + costs[2];
            dp[i] = Math.min(c1, Math.min(c7, c30));
        }

        return dp[lastDay];
    }
}

func mincostTickets(days []int, costs []int) int {
	travel := make(map[int]bool)
	lastDay := 0
	for _, d := range days {
		travel[d] = true
		if d > lastDay {
			lastDay = d
		}
	}

	dp := make([]int, lastDay+1)
	for i := 1; i <= lastDay; i++ {
		if !travel[i] {
			dp[i] = dp[i-1]
			continue
		}

		c1 := dp[max(0, i-1)] + costs[0]
		c7 := dp[max(0, i-7)] + costs[1]
		c30 := dp[max(0, i-30)] + costs[2]
		dp[i] = min3(c1, c7, c30)
	}

	return dp[lastDay]
}

func min3(a, b, c int) int {
	if a > b {
		a = b
	}
	if a > c {
		a = c
	}
	return a
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

相似题目

题目	难度	考察点
983. 最低票价	中等	DP
322. 零钱兑换	中等	DP
518. 零钱兑换 II	中等	DP
309. 买卖股票的最佳时机含冷冻期	中等	DP
740. 删除并获得点数	中等	DP
198. 打家劫舍	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/85625139