引言
青蛙过河是一道经典的算法面试题：河面上排列着若干石头，每块石头上标有青蛙在该位置能跳跃的最大距离，判断青蛙能否从起点到达终点。本文将这一问题扩展为最优路径规划版本——不仅判断是否可过河，还要找到跳跃次数最少、或总耗能最低的最优路径。通过贪心策略与动态规划的结合，实现不同约束条件下的最优决策。
问题定义与变体
基础版本（跳跃可达性）
给定数组stones[i]表示在第i块石头上最多能向前跳跃的步数，判断能否从第0块石头到达最后一块。
最优版本（最少跳跃次数）
在可达的前提下，找出到达终点所需的最少跳跃次数。例如[2,3,1,1,4]的最优解为2次（0→1→4）。
扩展版本（加权最优路径）
每块石头有额外属性（如跳跃耗能、停留风险），求总成本最低的路径。本文实现支持自定义成本函数的通用框架。
算法设计
贪心策略：最少跳跃次数
最少跳跃次数问题有经典的O(n)贪心解法：维护当前能到达的最远边界end，以及下一跳能到达的最远位置farthest。遍历数组时不断更新farthest，当到达当前end边界时，必须进行一次跳跃，并将end更新为farthest。
贪心正确性证明：假设存在更优解，在某一步没有选择能跳最远的石头，则可以用更远的选择替换，不会增加跳跃次数。
动态规划：加权最优路径
当每跳有自定义成本时，贪心不再适用。定义dp[i]为到达石头i的最小总成本：
dp[i] = min(dp[j] + cost(j, i)) for all j < i and j + stones[j] >= i
该DP的时间复杂度为O(n²)，可通过单调队列优化至O(n)。
Java完整实现
import java.util.*;
/**
* 青蛙过河最优路径规划
* 支持最少跳跃、加权最优、路径回溯等多种策略
*/
public class FrogJumpOptimizer {
private int[] stones;
private int n;
public FrogJumpOptimizer(int[] stones) {
this.stones = stones;
this.n = stones.length;
}
/**
* 基础版本：判断是否能到达终点
* 贪心维护最远可达距离
*/
public boolean canReach() {
int farthest = 0;
for (int i = 0; i < n; i++) {
if (i > farthest) return false; // 当前位置不可达
farthest = Math.max(farthest, i + stones[i]);
if (farthest >= n - 1) return true;
}
return farthest >= n - 1;
}
/**
* 贪心版本：最少跳跃次数
* 时间复杂度 O(n)，空间复杂度 O(1)
*/
public int minJumpsGreedy() {
if (n <= 1) return 0;
int jumps = 0;
int currentEnd = 0; // 当前跳跃能到达的最远边界
int farthest = 0; // 下一跳能到达的最远位置
for (int i = 0; i < n - 1; i++) {
// 更新下一跳的最远可达位置
farthest = Math.max(farthest, i + stones[i]);
// 到达当前边界，必须跳一次
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
// 提前终止检查
if (currentEnd >= n - 1) break;
}
}
return jumps;
}
/**
* 贪心版本附带路径回溯
* 记录每次跳跃的落点
*/
public Result minJumpsGreedyWithPath() {
if (n <= 1) return new Result(0, Arrays.asList(0));
int jumps = 0;
int currentEnd = 0;
int farthest = 0;
int bestNext = 0; // 下一跳的最佳落点
List<Integer> path = new ArrayList<>();
path.add(0);
for (int i = 0; i < n - 1; i++) {
int reach = i + stones[i];
if (reach > farthest) {
farthest = reach;
bestNext = i;
}
if (i == currentEnd) {
jumps++;
if (bestNext != path.get(path.size() - 1)) {
path.add(bestNext);
}
currentEnd = farthest;
if (currentEnd >= n - 1) {
path.add(n - 1);
break;
}
}
}
return new Result(jumps, path);
}
/**
* 动态规划：加权最优路径
* cost[i] 表示从石头i起跳的基础成本
*/
public Result weightedMinCost(int[] jumpCost) {
// dp[i] 表示到达i的最小总成本
int[] dp = new int[n];
int[] parent = new int[n]; // 记录前驱节点，用于回溯路径
Arrays.fill(dp, Integer.MAX_VALUE / 2);
Arrays.fill(parent, -1);
dp[0] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// 从j能跳到i
if (j + stones[j] >= i) {
int cost = dp[j] + jumpCost[j];
if (cost < dp[i]) {
dp[i] = cost;
parent[i] = j;
}
}
}
}
if (dp[n - 1] >= Integer.MAX_VALUE / 2) {
return new Result(-1, new ArrayList<>());
}
// 回溯路径
List<Integer> path = new ArrayList<>();
int cur = n - 1;
while (cur != -1) {
path.add(cur);
cur = parent[cur];
}
Collections.reverse(path);
return new Result(dp[n - 1], path);
}
/**
* 单调队列优化DP：最小跳跃次数（等价于每跳成本为1）
* 时间复杂度 O(n)，适用于大规模数据
*/
public int minJumpsDeque() {
if (n <= 1) return 0;
// dp[i] 表示到达i的最少跳跃次数
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE / 2);
dp[0] = 0;
// 双端队列维护候选跳跃源：dp值单调递增
Deque<Integer> deque = new LinkedList<>();
deque.addLast(0);
for (int i = 1; i < n; i++) {
// 移除不能跳到i的源（超出跳跃范围）
while (!deque.isEmpty() && deque.peekFirst() + stones[deque.peekFirst()] < i) {
deque.pollFirst();
}
if (deque.isEmpty()) {
dp[i] = Integer.MAX_VALUE / 2; // 不可达
continue;
}
// 队首就是最优源（最少跳跃次数）
dp[i] = dp[deque.peekFirst()] + 1;
// 维护单调性：移除dp值大于等于dp[i]的元素
while (!deque.isEmpty() && dp[deque.peekLast()] >= dp[i]) {
deque.pollLast();
}
deque.addLast(i);
}
return dp[n - 1] >= Integer.MAX_VALUE / 2 ? -1 : dp[n - 1];
}
/**
* 多约束优化：同时考虑跳跃次数和总距离
* 使用字典序比较：(jumps, totalDistance)
*/
public Result multiObjectiveOptimize() {
// 状态：(最少跳跃次数, 最小总跳跃距离)
int[] minJumps = new int[n];
int[] minDist = new int[n];
int[] parent = new int[n];
Arrays.fill(minJumps, Integer.MAX_VALUE / 2);
Arrays.fill(minDist, Integer.MAX_VALUE / 2);
Arrays.fill(parent, -1);
minJumps[0] = 0;
minDist[0] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (j + stones[j] >= i) {
int dist = i - j; // 本次跳跃距离
int newJumps = minJumps[j] + 1;
int newDist = minDist[j] + dist;
// 字典序优化：先比跳跃次数，再比总距离
if (newJumps < minJumps[i] ||
(newJumps == minJumps[i] && newDist < minDist[i])) {
minJumps[i] = newJumps;
minDist[i] = newDist;
parent[i] = j;
}
}
}
}
if (minJumps[n - 1] >= Integer.MAX_VALUE / 2) {
return new Result(-1, new ArrayList<>());
}
List<Integer> path = new ArrayList<>();
int cur = n - 1;
while (cur != -1) {
path.add(cur);
cur = parent[cur];
}
Collections.reverse(path);
System.out.println("Multi-objective result: jumps=" + minJumps[n-1]
+ ", totalDistance=" + minDist[n-1]);
return new Result(minJumps[n - 1], path);
}
/**
* 打印跳跃可视化
*/
public void visualizePath(List<Integer> path) {
char[] line = new char[n];
Arrays.fill(line, '-');
for (int i = 0; i < n; i++) {
line[i] = (char) ('0' + (stones[i] % 10));
}
System.out.println("Stones: " + Arrays.toString(stones));
System.out.print("Path: ");
for (int i = 0; i < n; i++) {
if (path.contains(i)) {
System.out.print("^");
} else {
System.out.print(" ");
}
if (i < n - 1) System.out.print(" ");
}
System.out.println();
}
static class Result {
int value;
List<Integer> path;
Result(int v, List<Integer> p) { this.value = v; this.path = p; }
}
public static void main(String[] args) {
int[] stones = {2, 3, 1, 1, 4, 2, 1, 3, 2, 1};
FrogJumpOptimizer solver = new FrogJumpOptimizer(stones);
System.out.println("=== Frog Jump Optimizer Demo ===\n");
System.out.println("Stones: " + Arrays.toString(stones));
// 基础可达性
System.out.println("\n1. Can reach end? " + solver.canReach());
// 贪心最少跳跃
int greedyJumps = solver.minJumpsGreedy();
System.out.println("\n2. Greedy min jumps: " + greedyJumps);
// 贪心附带路径
Result greedyPath = solver.minJumpsGreedyWithPath();
System.out.println("\n3. Greedy path: jumps=" + greedyPath.value
+ ", path=" + greedyPath.path);
solver.visualizePath(greedyPath.path);
// 单调队列优化
int dequeJumps = solver.minJumpsDeque();
System.out.println("\n4. Deque optimized min jumps: " + dequeJumps);
// 加权最优路径（假设每块石头的跳跃成本为stones[i]）
int[] costs = Arrays.copyOf(stones, stones.length);
Result weighted = solver.weightedMinCost(costs);
System.out.println("\n5. Weighted min cost (cost=stones[i]): cost=" + weighted.value
+ ", path=" + weighted.path);
solver.visualizePath(weighted.path);
// 多目标优化
Result multi = solver.multiObjectiveOptimize();
System.out.println("\n6. Multi-objective path: " + multi.path);
solver.visualizePath(multi.path);
}
}
算法复杂度对比
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 可达性判断 | O(n) | O(1) | 仅需判断能否过河 |
| 贪心最少跳跃 | O(n) | O(1) | 无权重，仅求最少次数 |
| 基础DP | O(n²) | O(n) | 带权重的最优路径 |
| 单调队列优化DP | O(n) | O(n) | 大规模数据的最少跳跃 |
| 多目标DP | O(n²) | O(n) | 多约束平衡优化 |
关键设计要点
- 贪心最优性保证：最少跳跃问题的贪心策略基于”当前边界内选最远”原则，严格优于或等于任何其他选择的后续表现
- 单调队列优化：维护候选源点的双端队列，利用”若j在i之前且dp[j] ≤ dp[i]，则i在后续决策中永优j”的性质，将O(n²)降至O(n)
- 路径回溯机制：parent数组记录前驱节点，支持从终点反向重构完整决策链
- 多目标字典序：通过按优先级依次比较目标值，将多目标问题转化为可比较的单目标问题
总结
青蛙过河问题虽小，却涵盖了贪心、动态规划、单调队列优化等核心算法思想。本文从基础判断延伸至多目标最优路径，展示了如何针对同一问题在不同约束条件下选择最合适的算法策略。读者可进一步尝试将贪心与DP结合，或引入A*启发式搜索处理带地形障碍的二维过河场景。
