403. 青蛙过河

题目描述

一只青蛙要过河。河面被分成若干单元格，有的格子上有石头。青蛙只能落在石头上，不能落进水里。

输入数组 stones，按严格递增顺序给出每块石头所在的格子编号，第一块石头在 0。青蛙一开始站在第一块石头上，第一跳只能跳 1 个单位。

如果上一跳跳了 k 个单位，下一跳只能跳 k - 1、k 或 k + 1 个单位。青蛙只能往前跳，跳跃距离必须为正。

判断青蛙能否最终落到最后一块石头上。能则返回 true，否则返回 false。

示例 1

输入：stones = [0,1,3,5,6,8,12,17]
输出：true

解释：依次跳 1,2,2,3,4,5 个单位，可以到达位置 17。

示例 2

输入：stones = [0,1,2,3,4,8,9,11]
输出：false

解释：到达位置 4 时上一跳最多为 2 个单位，下一跳最多 3，跳不到位置 8。

数据范围

2 <= stones.length <= 2000
0 <= stones[i] <= 2^31 - 1
stones[0] == 0
stones 严格递增

解题思路：动态规划（哈希集合）

青蛙下一步能跳多远，只取决于它站在哪块石头上、以及上一跳的距离 k。所以状态是“石头 s + 到达它的最后一跳 k”。dp[s] 记录到达 s 的所有可能 k。从左到右处理石头：s 左边的石头都已处理完，dp[s] 已经完整；对每个 k 尝试 k-1、k、k+1，若落点是石头就把这一跳加入落点的集合。最后看终点集合是否非空。

为什么正确

处理到石头 s 时，dp[s] 已经包含所有能到达 s 的最后一跳距离，因为所有能跳到 s 的石头都在它左边，已被处理过。

复杂度分析

时间 O(n^2)：每块石头最多有 O(n) 种 k，每种尝试 3 个落点。空间 O(n^2)。

易错点

只记录“能否到达某块石头”是不够的：到达方式不同，上一跳 k 不同，后续能跳的距离也不同。另外 step 必须大于 0，否则 k=1 时会出现原地跳 0。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        dp = {s: set() for s in stones}
        dp[0].add(0)
        for s in stones:
            for k in dp[s]:
                for step in (k - 1, k, k + 1):
                    if step > 0 and s + step in dp:
                        dp[s + step].add(step)
        return len(dp[stones[-1]]) > 0

class Solution {
    public boolean canCross(int[] stones) {
        Map<Long, Set<Integer>> dp = new HashMap<>();
        for (int s : stones) {
            dp.put((long) s, new HashSet<>());
        }
        dp.get(0L).add(0);
        for (int s : stones) {
            for (int k : dp.get((long) s)) {
                for (int step : new int[]{k - 1, k, k + 1}) {
                    long t = (long) s + step;
                    if (step > 0 && dp.containsKey(t)) {
                        dp.get(t).add(step);
                    }
                }
            }
        }
        return dp.get((long) stones[stones.length - 1]).size() > 0;
    }
}

class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_map<long long, unordered_set<int>> dp;
        for (int s : stones) {
            dp[s];
        }
        dp[0].insert(0);
        for (int s : stones) {
            for (int k : dp[s]) {
                for (int step : {k - 1, k, k + 1}) {
                    if (step > 0 && dp.count((long long)s + step)) {
                        dp[(long long)s + step].insert(step);
                    }
                }
            }
        }
        return !dp[stones.back()].empty();
    }
};

func canCross(stones []int) bool {
	dp := map[int]map[int]bool{}
	for _, s := range stones {
		dp[s] = map[int]bool{}
	}
	dp[0][0] = true
	for _, s := range stones {
		for k := range dp[s] {
			for _, step := range []int{k - 1, k, k + 1} {
				if _, ok := dp[s+step]; step > 0 && ok {
					dp[s+step][step] = true
				}
			}
		}
	}
	return len(dp[stones[len(stones)-1]]) > 0
}

var canCross = function(stones) {
    const dp = new Map();
    for (const s of stones) {
        dp.set(s, new Set());
    }
    dp.get(0).add(0);
    for (const s of stones) {
        for (const k of dp.get(s)) {
            for (const step of [k - 1, k, k + 1]) {
                if (step > 0 && dp.has(s + step)) {
                    dp.get(s + step).add(step);
                }
            }
        }
    }
    return dp.get(stones[stones.length - 1]).size > 0;
};

function canCross(stones: number[]): boolean {
    const dp = new Map<number, Set<number>>();
    for (const s of stones) {
        dp.set(s, new Set());
    }
    dp.get(0)!.add(0);
    for (const s of stones) {
        for (const k of dp.get(s)!) {
            for (const step of [k - 1, k, k + 1]) {
                if (step > 0 && dp.has(s + step)) {
                    dp.get(s + step)!.add(step);
                }
            }
        }
    }
    return dp.get(stones[stones.length - 1])!.size > 0;
}

载入编辑器，自己跑一遍 →

其他解法

主解法自底向上推出每块石子能用哪些步长到达；记忆化搜索自顶向下尝试跳法，遇到可行路线就提前结束，两者状态数相同。

解法 2：记忆化搜索时间 O(n²)，空间 O(n²)

先用哈希表记录每个石子位置对应的下标。dfs(i, last) 表示青蛙站在第 i 块石子、上一步跳了 last 个单位时能否到达终点。依次尝试 last - 1、last、last + 1 三种跳法，目标位置有石子就递归。把失败的状态记下来，再次遇到时直接返回 false。

从起点出发只搜索真正可达的状态，找到一条路线就立即返回。递归深度最多为石子数，Python 需要调高递归深度上限。

import sys


class Solution:
    def canCross(self, stones):
        sys.setrecursionlimit(10000)
        n = len(stones)
        pos = {s: i for i, s in enumerate(stones)}
        failed = set()

        def dfs(i, last):
            if i == n - 1:
                return True
            if (i, last) in failed:
                return False
            for step in (last - 1, last, last + 1):
                if step > 0 and stones[i] + step in pos:
                    if dfs(pos[stones[i] + step], step):
                        return True
            failed.add((i, last))
            return False

        return dfs(0, 0)

class Solution {
    int n;
    int[] st;
    Map<Long, Integer> pos = new HashMap<>();
    Set<Long> failed = new HashSet<>();

    boolean dfs(int i, int last) {
        if (i == n - 1) return true;
        long key = (long) i * (n + 1) + last;
        if (failed.contains(key)) return false;
        for (int step = last - 1; step <= last + 1; step++) {
            if (step <= 0) continue;
            Integer j = pos.get((long) st[i] + step);
            if (j != null && dfs(j, step)) return true;
        }
        failed.add(key);
        return false;
    }

    public boolean canCross(int[] stones) {
        st = stones;
        n = stones.length;
        for (int i = 0; i < n; i++) pos.put((long) stones[i], i);
        return dfs(0, 0);
    }
}

class Solution {
public:
    int n;
    vector<int> st;
    unordered_map<long long, int> pos;
    unordered_set<long long> failed;
    bool dfs(int i, int last) {
        if (i == n - 1) return true;
        long long key = (long long)i * (n + 1) + last;
        if (failed.count(key)) return false;
        for (int step = last - 1; step <= last + 1; step++) {
            if (step <= 0) continue;
            auto it = pos.find((long long)st[i] + step);
            if (it != pos.end() && dfs(it->second, step)) return true;
        }
        failed.insert(key);
        return false;
    }
    bool canCross(vector<int>& stones) {
        st = stones;
        n = stones.size();
        for (int i = 0; i < n; i++) pos[stones[i]] = i;
        return dfs(0, 0);
    }
};

func canCross(stones []int) bool {
	n := len(stones)
	pos := map[int]int{}
	for i, s := range stones {
		pos[s] = i
	}
	failed := map[[2]int]bool{}
	var dfs func(i, last int) bool
	dfs = func(i, last int) bool {
		if i == n-1 {
			return true
		}
		if failed[[2]int{i, last}] {
			return false
		}
		for step := last - 1; step <= last+1; step++ {
			if step <= 0 {
				continue
			}
			if j, ok := pos[stones[i]+step]; ok && dfs(j, step) {
				return true
			}
		}
		failed[[2]int{i, last}] = true
		return false
	}
	return dfs(0, 0)
}

var canCross = function(stones) {
    const n = stones.length;
    const pos = new Map();
    stones.forEach((s, i) => pos.set(s, i));
    const failed = new Set();
    const dfs = (i, last) => {
        if (i === n - 1) return true;
        const key = i * (n + 1) + last;
        if (failed.has(key)) return false;
        for (let step = last - 1; step <= last + 1; step++) {
            if (step <= 0) continue;
            const j = pos.get(stones[i] + step);
            if (j !== undefined && dfs(j, step)) return true;
        }
        failed.add(key);
        return false;
    };
    return dfs(0, 0);
};

function canCross(stones: number[]): boolean {
    const n = stones.length;
    const pos = new Map<number, number>();
    stones.forEach((s, i) => pos.set(s, i));
    const failed = new Set<number>();
    const dfs = (i: number, last: number): boolean => {
        if (i === n - 1) return true;
        const key = i * (n + 1) + last;
        if (failed.has(key)) return false;
        for (let step = last - 1; step <= last + 1; step++) {
            if (step <= 0) continue;
            const j = pos.get(stones[i] + step);
            if (j !== undefined && dfs(j, step)) return true;
        }
        failed.add(key);
        return false;
    };
    return dfs(0, 0);
}

动态规划专题的其他题目

查看动态规划全部题目 →