LeetCode 403. Frog Jump

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool canCross(vector<int>& stones) {
        const int n = stones.size();
        vector<unordered_map<int, bool>> m(n);
        function<bool(int, int)> dfs = [&](int i, int lastDist) {
            // `i` is current position, `lastDist` is the distance that frog jump over to get to `i`.
            if (i == n - 1) return true;
            if (m[i].find(lastDist) != m[i].end()) return m[i][lastDist];
            for (int currDist = lastDist - 1; currDist <= lastDist + 1; ++currDist) {
                if (currDist > 0) {
                    int j = lower_bound(stones.begin(), stones.end(), currDist + stones[i]) - stones.begin();
                    if (j != n && stones[j] == stones[i] + currDist && dfs(j, currDist)) {
                        return m[i][lastDist] = true;
                    }
                }
            }
            return m[i][lastDist] = false;
        };
        return dfs(0, 0);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool canCross(vector<int>& stones) {
        const int n = stones.size();
        for (int i = 1; i < n; ++i)
            if (stones[i] - stones[i - 1] > i)
                return false;
        // dp[i][k] stands for whether frog can jump to `i` from `j` with distance `k`,
        // so dp[i][k] = dp[j][k − 1] || dp[j][k] || dp[j][k + 1].
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        dp[0][0] = true;
        for (int i = 1; i < n; ++i)
            for (int j = i - 1; j >= 0; --j) {
                int k = stones[i] - stones[j];
                if (k > j + 1)
                    break;
                dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
                if (i == n - 1 && dp[i][k])
                    return true;
            }
        return false;
    }
};