LeetCode 403. Frog crossing the river daily

Problem description

A frog wants to cross the river . Suppose the river is divided equally into cells , And there may be a stone in each cell （ Maybe not ）. Frogs can jump on stones , But don't jump into the water .

Here's a list of the locations of the stones stones（ Use cell number Ascending Express ）,  Please judge whether the frog can cross the river successfully （ That is, whether we can jump to the last stone at the last step ）. At the beginning of the ,  The frog stands on the first stone by default , And it can be assumed that its first step can only jump 1 A unit of （ That is, only from cells 1 Jump to cell 2 ）.

If the frog jumps last  k  A unit of , Then its next jump distance can only be chosen as  k - 1、k  or  k + 1 A unit of .  Attention, please. , Frogs can only move forward （ The direction of the destination ） jumping .

Example 1：

Input ：stones = [0,1,3,5,6,8,12,17]
Output ：true
explain ： Frogs can cross the river successfully , Jump as follows ： jump 1 Units to 2 Block stone , Then jump 2 Units to 3 Block stone , next jump 2 Units to 4 Block stone , Then jump 3 Units to 6 Block stone , jump 4 Units to 7 Block stone , Last , jump 5 Units to 8 A stone （ The last stone ）.
Example 2：

Input ：stones = [0,1,2,3,4,8,9,11]
Output ：false
explain ： This is because of the 5 And the 6 The space between the stones is too big , There is no alternative for frogs to jump over .
 

Tips ：

2 <= stones.length <= 2000
0 <= stones[i] <= 231 - 1
stones[0] == 0
stones  In strict ascending order

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/frog-jump
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Java

class Solution {
    public boolean canCross(int[] stones) {
        int n = stones.length;
        boolean[][] dp = new boolean[n + 1][n + 1];
        dp[0][0] = true;

        for(int i = 1;i < n;i++){
            for(int j = 0;j < i;j++){
                // From j Stone to i The minimum step size of a stone is k
                int k = stones[i] - stones[j];
                // The first j The maximum step length of a stone is j + 1
                if(k <= j + 1){
                    // Can it be in steps k The speed reaches the i A stone 
                    dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
                }
            }
        }
        for(int i = 1;i <= n;i++){
            if(dp[n - 1][i]) return true;
        }
        return false;
    }
}