403. 青蛙过河

Smile_slime_47
  1999-01-01 1999-01-01 Created    

原题地址：https://leetcode.cn/problems/frog-jump/?envType=study-plan-v2&id=dynamic-programming-grandmaster

题解

设dp[i][j]为第i个石头能否经过j步跳到该石头上，由于每次跳跃距离最多只能比前一次跳跃递增1，而对于n个石头最多只能跳跃n-1次，实际上对于整个数组而言，跳跃距离最大不会超过n（在每一次都选择递增的极端情况下）

因此虽然给出的石头坐标很恐怖（Interget.MAX_VALUE），但是实际上用stones.length足以表示最大的跳跃距离

我们遍历i，对于大于i的第j个石头，其距离为**stones[j]-stones[i]**，当

  • dp[i][stones[j]-stones[i]]
  • dp[i][stones[j]-stones[i]+1]
  • dp[i][stones[j]-stones[i]-1]

这三者中的任意一种为true时，我们都可以从第i个石头跳跃到第j个石头上，此时就可至dp[j][stones[j]-stones[i]]为true;

当j和i的距离大于等于stones.length时，由于上述结论，已经不存在从i跳跃到j的可能性，此时可以直接break

考虑边界情况：

  • 对于dp[0]，我们不应当至dp[0][1]为true，因为这样dp可以选择跳1格或者跳2格，由题可知第0个石头最多只能跳跃1格，因此应当设置dp[0][0]为true

时间复杂度：O(N^2)

空间复杂度：O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean canCross(int[] stones) {
        boolean flag=false;
        boolean[][] dp=new boolean[stones.length][stones.length+1];
        dp[0][0]=true;
        for(int i=0;i<dp.length;i++){
            for(int j=i+1;j<stones.length&&stones[j]-stones[i]<stones.length;j++){
                if(dp[i][stones[j]-stones[i]]||dp[i][stones[j]-stones[i]-1]||dp[i][stones[j]-stones[i]+1]){
                    dp[j][stones[j]-stones[i]]=true;
                    if(j==dp.length-1){
                        flag=true;
                        break;
                    }
                }
            }
            if(flag)break;
        }
        return flag;
    }
}
Comments
On this page
403. 青蛙过河
  1. 题解