[leetcode] Frog Jump

题目地址
A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.
If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

题目大意：
青蛙一次跳多少由上一次跳多少决定，上一次跳了k步，那么这次可以跳k-1,k,k+1这么多。从0开始，第一次只能跳一步，问能否调到最后一个石头上面。

明显的dp题，我们用f[i][j]表示到第i个时候，跳j步是否可以达到。那么明显的
f[i][j] =f[k][j-1] || f[k][j] || f[k][j+1]
其中j是i和k的间隙，既 j = stones[i] - stones[k]
还有个问题，我也是交了一次才返现，数据是[0, 2^31-1]
按我们的做法明显就Runtime Error啦，其实这里j有个上限，假如我们有n个石头，那么有n-1个间隙，第一次是1步，然后每次+1，也就是
1,2,3,4,5,n-1
其实最多一次就跳n-1嘛，如果有间隙大于n-1那肯定是没结果的，我们就无视它吧。

class Solution {
public:
    bool canCross(vector<int>& stones) {
        if (stones.size() == 0) return true;
        vector<vector<bool>> f(stones.size(), vector<bool>(stones.size(), false));
        
        f[0][0] = true;
        
        for (int i = 1; i < stones.size(); i++) {
            for (int j = 0; j < i; j++) {
                int k = stones[i] - stones[j];
                if (k >= stones.size()) continue;
                f[i][k] = f[j][k];
                if (k - 1 >= 0) f[i][k] = f[i][k] || f[j][k - 1];
                if (k + 1 < stones.size()) f[i][k] = f[i][k] || f[j][k + 1];
            }
        }
        bool ans = false;
        for (int i = 0; i < stones.size(); i++) {
            ans = ans || f[stones.size() - 1][i];
        }
        return ans;
    }
};

提交了上面的代码第一次运气好就过了，然后第二次就TLE，其实还有个优化的地方，就是每次j循环并不用从0开始，可以用二分找到第一个让这个间隙小于等于n-1的地方
我们加上二分，虽然时间上没哟快多少，但是保证了不会偶尔TLE了，每次都能AC

class Solution {
public:
    bool canCross(vector<int>& stones) {
        if (stones.size() == 0) return true;
        vector<vector<bool>> f(stones.size(), vector<bool>(stones.size(), false));
        
        f[0][0] = true;
        
        for (int i = 1; i < stones.size(); i++) {
            int l = 0;
            int r = i - 1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (stones[i] - stones[mid] < stones.size()) r = mid - 1;
                else l = mid + 1;
            }
            for (int j = l; j < i; j++) {
                int k = stones[i] - stones[j];
                if (k >= stones.size()) continue;
                f[i][k] = f[j][k];
                if (k - 1 >= 0) f[i][k] = f[i][k] || f[j][k - 1];
                if (k + 1 < stones.size()) f[i][k] = f[i][k] || f[j][k + 1];
            }
        }
        bool ans = false;
        for (int i = 0; i < stones.size(); i++) {
            ans = ans || f[stones.size() - 1][i];
        }
        return ans;
    }
};