LeetCode-403 青蛙过河

短命女 2022-12-11 09:21 136阅读 0赞

[LeetCode403][]

*   d p \[ i \] \[ j \] dp\[i\]\[j\] dp\[i\]\[j\] 表示从 i i i点可以走 j j j步长
 *   d i s = s t o n e s \[ i \] − s t o n e s \[ j \] dis = stones\[i\] - stones\[j\] dis=stones\[i\]−stones\[j\] (dis是 j j j个石头到 i i i个石头的距离)
 *  如果 d p \[ j \] \[ d i s \] dp\[j\]\[dis\] dp\[j\]\[dis\]为true，表示 j j j点可以走 d i s dis dis长度，就是从 j j j点可以走到 i i i点
 *  既然可以走 d i s dis dis长度，继续再从 i i i点出发，那么根据题意，也可以走 d i s dis dis长度：
    
     *   d p \[ i \] \[ d i s − 1 \] dp\[i\]\[dis - 1\] dp\[i\]\[dis−1\] = true
     *   d p \[ i \] \[ d i s \] dp\[i\]\[dis\] dp\[i\]\[dis\] = true
     *   d p \[ i \] \[ d i s + 1 \] dp\[i\]\[dis + 1\] dp\[i\]\[dis\+1\] = true

class Solution {
        
        public boolean canCross(int[] stones) {
        
            // dp[i][j]表示可以从i点跳j步
            boolean[][] dp = new boolean[1110][1110];
    
            dp[0][1] = true;
    
            for (int i=1; i<stones.length; i++){
        
    
                boolean flag = false;
    
                for (int j=i-1; j>=0; j--){
        
                    int dis = stones[i] - stones[j];        // i和j之间的距离
    
                    if (dis > i){
        
                        // 超出长度了，后面的点只会越来越远
                        break;
                    }
                    if (dp[j][dis]){
            // 如果可以从j跳dis长度（到当前点）
                        dp[i][dis-1] = true;        // 那么也可以从当前点跳k-1,k,k+1长度
                        dp[i][dis] = true;
                        dp[i][dis+1] = true;
                        flag = true;
                    }
                }
                if (i == stones.length-1 && !flag){
         // 如果之前的所有点都跳不到i点，并且i就是终点
                    return false;
                }
            }
            return true;
        }
    }

[LeetCode403]: https://leetcode-cn.com/problems/frog-jump/