題目地址
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開始肋殴，第一次只能跳一步芽死，問能否調(diào)到最后一個石頭上面霸旗。
明顯的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]
還有個問題续挟，我也是交了一次才返現(xiàn)紧卒，數(shù)據(jù)是[0, 2^31-1]
按我們的做法明顯就Runtime Error啦，其實這里j有個上限诗祸，假如我們有n個石頭跑芳，那么有n-1個間隙，第一次是1步直颅，然后每次+1博个，也就是
1,2,3,4,5,n-1
其實最多一次就跳n-1嘛，如果有間隙大于n-1那肯定是沒結(jié)果的功偿，我們就無視它吧盆佣。
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械荷，其實還有個優(yōu)化的地方共耍，就是每次j循環(huán)并不用從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;
}
};
