🌕🌕 403. 青蛙过河

难度: 🌕🌕

问题描述

---

解法

class Solution {
    public boolean canCross(int[] stones) {
        // 思路：
        // dp[i][j] - 从 [i] 能否到达跳 j 步
        int len = stones.length;
        boolean[][] dp = new boolean[len][len];
        // 初始化
        dp[0][0] = true;
        // dp
        for(int i = 1; i < len; i ++) { // 当前处于的下标位置
            for(int j = i - 1; j >= 0; j --) { // 上一次可能处于的下标位置
                int step = stones[i] - stones[j]; // 从 [j] 到达 [i] 需要走的步数
                // 从 [j] 出发，最多能走 j + 1 步
                if(step > j + 1) {
                    break; // 从 [j] 处走不能到达，前面的节点也不可能到达，跳出当前循环
                }
                // 判断 dp[i][step] 是否成立，即在 [i] 处能否走 step 步
                dp[i][step] = dp[j][step - 1] || dp[j][step] || dp[j][step + 1];
                // 只要有一种情况能到达目标节点，即可返回
                if(dp[len - 1][step]) {
                    return true;
                }
            }
        }
        return false;
    }
}

---

输出