Skip to content

403. Frog Jump 👍

Approach 1: Jump to

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  bool canCross(vector<int>& stones) {
    const int n = stones.size();
    // dp[i][j] := true if a frog can make a size j jump to stones[i]
    vector<vector<bool>> dp(n, vector<bool>(n + 1));
    dp[0][0] = true;

    for (int i = 1; i < n; ++i)
      for (int j = 0; j < i; ++j) {
        const int k = stones[i] - stones[j];
        if (k > n)
          continue;
        for (const int x : {k - 1, k, k + 1})
          if (0 <= x && x <= n)
            dp[i][k] = dp[i][k] || dp[j][x];
      }

    return ranges::any_of(dp.back(), [](bool val) { return val; });
  }
};

 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) {
    final int n = stones.length;
    // dp[i][j] := 1 if a frog can make a size j jump to stones[i]
    int[][] dp = new int[n][n + 1];
    dp[0][0] = 1;

    for (int i = 1; i < n; ++i)
      for (int j = 0; j < i; ++j) {
        final int k = stones[i] - stones[j];
        if (k > n)
          continue;
        for (final int x : new int[] {k - 1, k, k + 1})
          if (0 <= x && x <= n)
            dp[i][k] |= dp[j][x];
      }

    return Arrays.stream(dp[n - 1]).anyMatch(a -> a == 1);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def canCross(self, stones: list[int]) -> bool:
    n = len(stones)
    # dp[i][j] := True if a frog can make a size j jump to stones[i]
    dp = [[False] * (n + 1) for _ in range(n)]
    dp[0][0] = True

    for i in range(1, n):
      for j in range(i):
        k = stones[i] - stones[j]
        if k > n:
          continue
        for x in (k - 1, k, k + 1):
          if 0 <= x <= n:
            dp[i][k] |= dp[j][x]

    return any(dp[-1])

Approach 2: Jump from

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  bool canCross(vector<int>& stones) {
    const int n = stones.size();
    // dp[i][j] := true if a frog can make a size j jump from stones[i]
    vector<vector<bool>> dp(n, vector<bool>(n + 1));
    dp[0][1] = true;

    for (int i = 1; i < n; ++i)
      for (int j = 0; j < i; ++j) {
        const int k = stones[i] - stones[j];
        if (k <= n && dp[j][k]) {
          dp[i][k - 1] = true;
          dp[i][k] = true;
          dp[i][k + 1] = true;
        }
      }

    return ranges::any_of(dp.back(), [](bool val) { return val; });
  }
};

 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) {
    final int n = stones.length;
    // dp[i][j] := 1 if a frog can make a size j jump from stones[i]
    int[][] dp = new int[n][n + 1];
    dp[0][1] = 1;

    for (int i = 1; i < n; ++i)
      for (int j = 0; j < i; ++j) {
        final int k = stones[i] - stones[j];
        if (k <= n && dp[j][k] == 1) {
          dp[i][k - 1] = 1;
          dp[i][k] = 1;
          dp[i][k + 1] = 1;
        }
      }

    return Arrays.stream(dp[n - 1]).anyMatch(a -> a == 1);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def canCross(self, stones: list[int]) -> bool:
    n = len(stones)
    # dp[i][j] := True if a frog can make a size j jump from stones[i]
    dp = [[False] * (n + 1) for _ in range(n)]
    dp[0][1] = True

    for i in range(1, n):
      for j in range(i):
        k = stones[i] - stones[j]
        if k <= n and dp[j][k]:
          dp[i][k - 1] = True
          dp[i][k] = True
          dp[i][k + 1] = True

    return any(dp[-1])