LeetCode 补充题 180. 过桥的最少踩石数
题目描述
牛客原题： ✅ 补充题 180. 过桥的最少踩石数
桥长
L <= 10^9，从0开始，每次向右跳S…T个单位，1 <= S <= T <= 10。到达或越过L即完成。桥上最多
100颗石子，起终点没有石子。返回最少踩到多少颗。
示例 1：
输入：
L = 10, S = 2, T = 3, stones = [2,3,5,6,7]
输出：2
解释： 可沿0→2→4→7→10跳跃，仅踩到位置2、7的石子。
提示：
-
1≤L≤10^9，1≤S≤T≤10。 - 最多
100颗石子，起点和终点没有石子。 - 到达或越过
L即完成，不要求恰好落在L。
题意分析
桥长可达十亿，不能直接对每个原始坐标做动态规划，但石子只有至多 100 颗。代价只在落到石子时增加，足够长的无石子间隔只负责连接两侧，可以先压缩这些间隔。
固定步长
S == T时落点余数无法改变，不能随意缩短间隔；直接统计石子中位置为S倍数的点即可。
解法：压缩长空段后做落点 DP
核心思路
[!blue]
S < T时至少能跳S和S+1。任意D >= S(S-1)，写成D = qS+r后有q >= r，可改写为(q-r)S+r(S+1)，所以足够长的空段中不再存在不可达的距离余数。对相邻石子以及末石子到桥尾的间隔，保留至多
T²。这个长度在扣除空段两侧一次跳跃所影响的边界范围后，仍覆盖上述连续可达阈值，因而保留两端落点间的连接能力，同时不增加踩石代价。压缩后
dp[x]表示恰好落在位置x的最少踩石数，初始只有dp[0]=0可达。从x-step转移，当前位置有石子才加 1。完成条件是到达或越过桥尾，最后一跳最多长T，所以答案取[end,end+T-1]的最小值，而不是只取dp[end]。
解题步骤
- S=T 时只统计位于步长整数倍处的石子。
- 其余情况排序石子，把每段空隙截到 T²，并处理最后一颗石子到桥尾的间距。
- 用 dp[x] 表示落在 x 的最小踩石子数，从 x-T 至 x-S 转移。
- 首次越过桥尾只可能落在终点至终点+T-1，取其中最小值。
代码实现
class Solution {
public int minStones(int length, int s, int t, int[] stones) {
if (s == t) {
int count = 0;
for (int x : stones) {
if (x % s == 0) {
count++;
}
}
return count;
}
Arrays.sort(stones);
int cap = t * t;
int position = 0;
int previous = 0;
Set<Integer> marked = new HashSet<>();
for (int x : stones) {
position += Math.min(cap, x - previous);
marked.add(position);
previous = x;
}
int end = position + Math.min(cap, length - previous);
int[] dp = new int[end + t];
Arrays.fill(dp, stones.length + 1);
dp[0] = 0;
for (int i = 1; i < dp.length; i++) {
for (int step = s; step <= t && step <= i; step++) {
dp[i] = Math.min(dp[i], dp[i - step] + (marked.contains(i) ? 1 : 0));
}
}
int answer = stones.length + 1;
for (int i = end; i < dp.length; i++) {
answer = Math.min(answer, dp[i]);
}
return answer;
}
}
import "sort"
func minStones(length, s, t int, stones []int) int {
if s == t {
count := 0
for _, x := range stones {
if x%s == 0 {
count++
}
}
return count
}
sort.Ints(stones)
cap, position, previous := t*t, 0, 0
marked := map[int]bool{}
for _, x := range stones {
position += min(cap, x-previous)
marked[position] = true
previous = x
}
end := position + min(cap, length-previous)
dp := make([]int, end+t)
for i := range dp {
dp[i] = len(stones) + 1
}
dp[0] = 0
for i := 1; i < len(dp); i++ {
cost := 0
if marked[i] {
cost = 1
}
for step := s; step <= t && step <= i; step++ {
dp[i] = min(dp[i], dp[i-step]+cost)
}
}
answer := len(stones) + 1
for i := end; i < len(dp); i++ {
answer = min(answer, dp[i])
}
return answer
}
复杂度分析
- 时间复杂度：$O(M \log (M+1)+(M+1)T^3)$；S=T 的分支只需 $O(M)$ 时间。
- 空间复杂度：额外空间 $O((M+1)T^2)$；S=T 的分支只需 $O(1)$ 额外空间。
设 M 为石子数。压缩后的坐标长度为 $O((M+1)T^2)$，包含桥尾的最后一段。
关键点总结
[!green]
S<T 时可以使用连续跳长 S、S+1；任意 D≥S(S-1) 可写成 qS+r，其中 q≥r，再改写为 (q-r)S+r(S+1)。T² 足够保留空段两侧边界窗口并连接中间可达距离，因此截短足够长的无石子空段不会改变最优踩石子数。
易错点总结
[!yellow]
不能按原L分配数组；固定步长时不可随意压缩余数；到达或越过终点都算成功。T²覆盖S与S+1形成连续可达距离的阈值及两侧至多T个位置的边界偏移。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 746. 使用最小花费爬楼梯 | 简单 | 都把踩到位置的代价放入状态转移，本题允许跳长范围且需先压缩巨大坐标。 |
| 403. 青蛙过河 | 困难 | 同样研究跳跃可达性，原题只能落在石子上，本题空位置也能落且踩石子才计成本。 |