LeetCode 403. 青蛙过河

题目描述：
一只青蛙想要过河。河流被分成若干单位宽度的单元格，每个单元格可能放有一块石头（也可能没有）。青蛙可以跳到石头上，但不能跳入水中。给定一个按严格升序排列的石头位置列表（每个位置是单元格编号，从0开始），请确定青蛙是否能够通过落在最后一块石头上成功过河。青蛙的起跳点在第一块石头（位置0），第一跳必须跳跃1个单位。如果青蛙上次跳跃了k个单位，那么它下一次跳跃的长度只能是k-1、k或k+1。

解题过程：

1. 问题分析：

• 这是一个动态规划与搜索结合的问题
• 关键约束：每次跳跃距离只能在上次基础上±1
• 初始条件：从0开始，第一次必须跳1个单位
• 目标：到达最后一块石头

2. 状态定义：

• 定义dp[i][j]：表示能否以j的跳跃长度到达位置i的石头
• i表示石头位置在列表中的索引
• j表示到达该石头时的跳跃长度

3. 状态转移：

• 对于当前位置i，如果从位置k以跳跃长度step跳过来
• 那么需要满足：stones[i] - stones[k] = step
• 且step的值只能是dp[k]中某个有效跳跃长度±1或不变

4. 具体步骤：

步骤1：预处理

• 创建哈希表记录每个石头位置对应的索引
• 初始化dp数组，dp[i]是集合，记录能到达位置i的所有跳跃长度

步骤2：初始状态

• dp[0] = {0} // 从起点开始，跳跃长度为0（还没跳）

步骤3：状态转移

for i from 0 to n-1:
    for each step in dp[i]:
        for next_step in [step-1, step, step+1]:
            if next_step > 0:  // 跳跃长度必须为正
                next_stone = stones[i] + next_step
                if next_stone在石头列表中:
                    j = next_stone的索引
                    dp[j].add(next_step)

步骤4：检查结果

• 如果dp[n-1]不为空，说明能到达终点

5. 优化：

• 使用哈希表记录石头位置到索引的映射，快速查找
• 使用集合存储每个位置的可行跳跃长度
• 剪枝：当跳跃长度超过剩余距离时提前终止

6. 复杂度分析：

• 时间复杂度：O(n²)，n为石头数量
• 空间复杂度：O(n²)

这个算法的关键在于理解状态定义：记录到达每个位置时的所有可能跳跃长度，然后基于这些长度进行状态转移。