05 August 2008
一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。
给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。
开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格 1 跳至单元格 2 ）。
如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
/*
https://segmentfault.com/a/1190000007648898
有点类似于jump game， 只不过这里对步数有了隐形的要求，当前步数和之前步数有关。
如果我们用brute force的方法来解，每一步有三种可能，一共n个石头，时间复杂度就是O(3^n)。
这其中有很多步数是多余的，第i个石头无法从任何一个石头到达，那么我们应该立即中止搜寻。
还有一个石头可能由之前的多个石头到达，这又是可以优化的地方。
当前结果可由之前的结果得出，且有重复的搜索方法，就需要用DP。
暴力搜索其实可以通过的
*/
public boolean canCross(int[] stones) {
if (stones[1] != 1) {
return false;
}
int n = stones.length;
int[][] dp = new int[n][n];// for ith stones, j means maximun previous steps
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = -1;
}
}
return canCross(dp, stones, 0, 0, n);
}
private boolean canCross(int[][] dp, int[] stones, int i, int j, int n) {
if (dp[i][j] != -1) {
return dp[i][j] == 1;
}
if (i == n-1) {
dp[i][j] = 1;
return true;
}
for (int k = i + 1; k < n; k++) {
if (stones[k] < stones[i] + j - 1) {//too close
continue;
} else if (stones[k] > stones[i] + j + 1) {//too far
dp[i][j] = 0;
continue;
} else {// j-1, j, j+1 three possibility
if (canCross(dp, stones, k, stones[k] - stones[i], n)) {
dp[i][j] = 1;
return true;
}
}
}
dp[i][j] = 0;
return false;
}
}