Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

403. Frog Jump

Time: $O(n^2)$

Space: $O(n^2)$

			


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 any_of(begin(dp.back()), end(dp.back()),
                  [](bool val) { return val; });
  }
};




			


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);
  }
}




			


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])