LeetCode周记 EP15

字数统计: 2.8k字   |   阅读时长: 13分

前言

被最小问题爆杀的一周…

本周主题：动态规划、二分查找、记忆化搜索

题目：

Minimum Cost For Tickets

Minimum Cost For Tickets
You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365.
Train tickets are sold in three different ways:

  • a 1-day pass is sold for costs[0] dollars,
  • a 7-day pass is sold for costs[-1]
  • a 30-day pass is sold for costs[-1]

The passes allow that many days of consecutive travel.
For example, if we get a 7-day pass on day 2, then we can travel for 7 days: 2, 3, 4, 5, 6, 7, and 8.
Return the minimum number of dollars you need to travel every day in the given list of days.

无论记忆化搜索还是动态规划，都需要先划分子问题和定义状态转移。

假设第 100 天是旅行的最后一天，分类讨论：

  • 在第 100 天购买为期 1 天的通行证，接下来需要解决的问题为：1 到 99 天的最小花费。
  • 在第 94 天购买为期 7 天的通行证，接下来需要解决的问题为：1 到 93 天的最小花费。
  • 在第 71 天购买为期 30 天的通行证，接下来需要解决的问题为：1 到 70 天的最小花费。
    这些问题都是和原问题相似的、规模更小的子问题，可以用递归解决。

动态规划有「选或不选」和「枚举选哪个」两种基本思考方式。在做题时，可根据题目要求，选择适合题目的一种来思考。本题用到的是「枚举选哪个」。

根据上面的讨论，定义 $dfs(i)$ 表示 $1$ 到 $i$ 天的最小花费。如果第 $i$ 天不在 days 中，那么问题变成 $1$ 到 $i−1$ 天的最小花费，即 $dfs(i)=dfs(i−1)$

如果第 $i$ 天在 days 中，分类讨论：

  • 在第 $i$ 天购买为期 $1$ 天的通行证，接下来需要解决的问题为：$1$ 到 $i−1$ 天的最小花费，即 $dfs(i)=dfs(i−1)+costs[0]$。
  • 在第 $i−6$ 天购买为期 $7$ 天的通行证，接下来需要解决的问题为：$1$ 到 $i−7$ 天的最小花费，即 $dfs(i)=dfs(i−7)+costs[1]$。
  • 在第 $i−29$ 天购买为期 $30$ 天的通行证，接下来需要解决的问题为：$1$ 到 $i−30$ 天的最小花费，即 $dfs(i)=dfs(i−30)+costs[2]$。

这三种情况取最小值，就得到了 dfs(i)，即

递归边界：$dfs(i)=0$，其中 $i≤0$。此时没有要旅行的天数。

递归入口：$dfs(D)$，其中 $D=days[n−1]$ 是最后一天。为了方便翻译成递推，我们从最后一天开始思考。

记忆化搜索

采用递归+记忆化的方式自顶向下解决问题，所谓自顶向下，即从最终结果$dfs(D)$向下延伸至底层计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int lastDay = days[days.length - 1];
        boolean[] isTravel = new boolean[lastDay + 1];
        for (int d : days) {
            isTravel[d] = true;
        }
        int[] memo = new int[lastDay + 1];
        return dfs(lastDay, isTravel, costs, memo);
    }

    private int dfs(int i, boolean[] isTravel, int[] costs, int[] memo) {
        if (i <= 0) {
            return 0;
        }
        if (memo[i] > 0) { // 之前计算过
            return memo[i];
        }
        if (!isTravel[i]) {
            return memo[i] = dfs(i - 1, isTravel, costs, memo);
        }
        return memo[i] = Math.min(dfs(i - 1, isTravel, costs, memo) + costs[0],
                         Math.min(dfs(i - 7, isTravel, costs, memo) + costs[1],
                                  dfs(i - 30, isTravel, costs, memo) + costs[2]));
    }
}

动态规划

自底向上遍历，即从days数组的左侧开始，状态 $f[i]$ 的定义和 $dfs(i)$ 的定义是一样的，都表示 $1$ 到 $i$ 天的最小花费。

相应的递推式（状态转移方程）也和 dfs 一样：

由于 $f[0]=0$ 且负数 $i$ 的状态值也为 $0$，我们可以把负数 $i$ 视作 $0$，上式等价于

初始值 $f[0]=0$，翻译自递归边界 $dfs(0)=0$。答案为 $f[D]$，翻译自递归入口 $dfs(D)$。所谓自底向上，即先计算底层结果，最后获得最终答案 $f[D]$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int lastDay = days[days.length - 1];
        boolean[] isTravel = new boolean[lastDay + 1];
        for (int d : days) {
            isTravel[d] = true;
        }
        int[] f = new int[lastDay + 1];
        for (int i = 1; i <= lastDay; i++) {
            if (!isTravel[i]) {
                f[i] = f[i - 1];
            } else {
                f[i] = Math.min(f[i - 1] + costs[0],
                       Math.min(f[Math.max(i - 7, 0)] + costs[1],
                                f[Math.max(i - 30, 0)] + costs[2]));
            }
        }
        return f[lastDay];
    }
}

优化

对于本题，最理想的情况是时间复杂度仅与days数组的长度有关而与$D=days[n−1]$的大小无关。

重新定义 $f[i]$ 表示旅行了 $i$ 天的最小花费：

  • $f[0]$ 表示旅行 $0$ 天的最小花费，根据定义，$f[0]=0$。
  • $f[1]$ 表示旅行 $1$ 天的最小花费，也就是完成 $days[0]$ 的最小花费。
  • $f[2]$ 表示旅行 $2$ 天的最小花费，也就是完成 $days[0]$ 和 $days[1]$ 的最小花费。
  • 一般地，$f[i+1]$ 表示完成 $days[0]$ 到 $days[i]$ 的最小花费。

分类讨论：

  • 在 $days[i]$ 购买为期 $1$ 天的通行证，接下来需要解决的问题为：完成 $days[0]$ 到 $days[i−1]$ 的最小花费，即 $f[i+1]=f[i]+costs[0]$。
  • 在第 $days[j]$ 天购买为期 $7$ 天的通行证，满足 $days[j]+7>days[i]$（注意不是 ≥），接下来需要解决的问题为：完成 $days[0]$ 到 $days[j−1]$ 的最小花费，即 $f[i+1]=f[j]+costs[1]$。
  • 在第 $days[k]$ 天购买为期 $30$ 天的通行证，满足 $days[k]+30>days[i]$，接下来需要解决的问题为：完成 $days[0]$ 到 $days[k−1]$ 的最小花费，即 $f[i+1]=f[k]+costs[2]$。

这三种情况取最小值，就得到了 $f[i+1]$，即

其中：

  • $j$ 是满足 $days[j]>days[i]−7$ 的最小的 $j$。
  • $k$ 是满足 $days[k]>days[i]−30$ 的最小的 $k$。
    由于 $days$ 是有序数组，计算 $j$ 和 $k$ 可以用双指针（三指针）算法。初始值 $f[0]=0, j=0, k=0$。答案为 $f[n]$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int n = days.length;
        int[] f = new int[n + 1];
        int j = 0;
        int k = 0;
        for (int i = 0; i < n; i++) {
            int d = days[i];
            while (days[j] <= d - 7) {
                j++;
            }
            while (days[k] <= d - 30) {
                k++;
            }
            f[i + 1] = Math.min(f[i] + costs[0], Math.min(f[j] + costs[1], f[k] + costs[2]));
        }
        return f[n];
    }
}

Minimum Cost to Reach Destination in Time

题意：从起点到终点，判断是否可在maxTime内到达，并计算最小过路费。

注意：在$[1, maxTime]$中任一时间到达终点，所花费的过路费多少不一定，即时间与花费无关，因此需要计算全部后筛选出最小花费。

动态规划

我们用 $f[t][i]$ 表示使用恰好 $t$ 分钟到达城市 $i$ 需要的最少通行费总和。
在状态转移时，我们考虑最后一次通行是从城市 $j$ 到达城市 $i$ 的，那么有状态转移方程：

其中 $(j, i) \in E$ 表示城市 $j$ 与 $i$ 存在一条道路， $\operatorname{cost}(j, i)$ 表示这条道路的耗费时间。
最终的答案即为 $f[1][n-1], f[2][n-1], \cdots, f[\operatorname{maxTime}][n-1]$ 中的最小值。

初始状态为 $f[0][0]=passingFees[0]$, 即我们一开始位于 0 号城市, 需要交 $passingFees[0]$的通行费。

由于状态中存放最小值，因此对于其它的状态，我们可以在一开始赋予它们一个极大值 $\infty$ 。如果最终的答案为 $\infty$, 说明无法在 maxTime 及以内完成旅行, 返回 $-1$ 。

此外, 本题中的道路是以数组 $edges$ 的形式给定的, 在动态规划的过程中, 如果我们使用两重循环枚举 $t$ 和 $i$, 就不能利用 $edges$, 而需要使用额外的数据结构存储以 $i$ 为端点的所有道路。一种合理的解决方法是, 我们使用一重循环枚举 $t$, 另一重循环枚举 edges 中的每一条边 $(i, j, cost )$, 通过这条边更新 $f[t][i]$ 以及 $f[t][j]$ 的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int minCost(int maxTime, int[][] edges, int[] passingFees) {
        int n = passingFees.length;
        int[][] f = new int[maxTime + 1][n];
        for (int i = 0; i <= maxTime; i++) {
            Arrays.fill(f[i], Integer.MAX_VALUE);
        }
        f[0][0] = passingFees[0];
        for (int t = 1; t <= maxTime; t++) {
            for (int[] edge : edges) {
                int i = edge[0], j = edge[1], cost = edge[2];
                if (cost <= t) {
                    // 确保从前序更新过的状态转移，且双向都可以更新
                    if (f[t - cost][j] != Integer.MAX_VALUE) {
                        f[t][i] = Math.min(f[t][i], f[t - cost][j] + passingFees[i]);
                    }
                    if (f[t - cost][i] != Integer.MAX_VALUE) {
                        f[t][j] = Math.min(f[t][j], f[t - cost][i] + passingFees[j]);
                    }
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int t = 1; t <= maxTime; t++) {
            ans = Math.min(ans, f[t][n - 1]);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

Minimum Time to Complete Trips

Minimum Time to Complete Trips

You are given an array time where time[i] denotes the time taken by the ith bus to complete one trip.

Each bus can make multiple trips successively; that is, the next trip can start immediately after completing the current trip. Also, each bus operates independently; that is, the trips of one bus do not influence the trips of any other bus.

You are also given an integer totalTrips, which denotes the number of trips all buses should make in total. Return the minimum time required for all buses to complete at least totalTrips trips.

首先建立一个Map，其中key为时间，value为该时间对应的trip数量，假设该Map为m。假设当前存在的key为k1, k2, k3,...,kn，则对于时间t，完成的trip数量f(t)可如此计算：

可以发现f(t)具有单调性，故考虑二分查找。

二分查找

二分查找的下界为$1$，上界为运行时间最短的bus运行totalTrips趟所用时间。实际测试中使用Map的方法时空效率均不如直接使用time数组进行check，在重复bus不多的情况下可以选择不使用Map。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    Map<Integer, Integer> map;

    public long minimumTime(int[] time, int totalTrips) {
        // map
        map = new HashMap<>();
        for(int x:time) map.merge(x, 1, Integer::sum);
        // 二分查找下界与上界
        long l = 1;
        long r = (long) totalTrips * Arrays.stream(time).min().orElse(0);
        // 二分查找寻找满足要求的最小的 t
        while (l < r) {
            long mid = l + (r - l) / 2;
            if (check(mid, totalTrips)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    // 判断 t 时间内是否可以完成 totalTrips 趟旅途
    public boolean check(long t, int totalTrips) {
        long cnt = 0;
        for (int period : map.keySet()) {
            cnt += t / period * map.get(period);
        }
        return cnt >= totalTrips;
    }
}

参考文献

[1] https://leetcode.cn/problems/minimum-cost-for-tickets/solutions/2936177/jiao-ni-yi-bu-bu-si-kao-dpcong-ji-yi-hua-tkw4/?envType=daily-question&envId=2024-10-01
[2] https://leetcode.cn/problems/minimum-cost-to-reach-destination-in-time/solutions/869919/gui-ding-shi-jian-nei-dao-da-zhong-dian-n3ews/?envType=daily-question&envId=2024-10-03

后记

首发于 silencezheng.top，转载请注明出处。

赏

谢谢打赏哟！

支付宝
微信

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

SilenceZheng66<br><br>记录所学技术<br>谢谢浏览