Least Jumps of Frog Cross River - 我的博客 - ITeye技术网站

Least Jumps of Frog Cross River - 我的博客 - ITeye技术网站
跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
头上。问最少几步可以跳完整条河流。

给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
第一步先提速到2，再跳到R[2]；
第二步先提速到3，再跳到R[5]；
第三步保持速度3，跳出数组范围，成功过河。
http://www.mitbbs.com/article_t1/JobHunting/32617501_0_1.html

DP状态方程：f(i,j) = min( f(i-j, j), f(i-j, j-1) ) + 1

i: 当前石头在数组中所处的index (0 based)

j: 到达i时的可能最大步数, <= sqrt(i*2) 假设处处有石子，那么青蛙可以随意跳跃，每次跳跃步伐比前一次跳跃大1，就有1+2+..+j = j(j+1)/2 = i, j^2+j = i*2, 所以 j <= sqrt(i*2) 

f(i, j): 以步数j到达i时所需的最少跳跃次数，其中f(0,1)=0

时间和空间复杂度均为O(n^(3/2))

1. public int minFrogJumps(int[] a) {  
2.     int len = a.length;  
3.     int[][] f = new int[len][(int)Math.sqrt(len * 2) + 1];  
4.     int ans = Integer.MAX_VALUE;  
5.     for (int i = 1; i < len; i++) {  
6.         Arrays.fill(f[i], -1);  
7.         if (a[i] == 0)  {  
8.             continue;  
9.         }  
10.         for (int j = 1; j <= (int)Math.sqrt(i * 2); j++) {  
11.             if (a[i - j] == 0) {  
12.                 f[i][j] = -1;  
13.                 continue;  
14.             }  
15.             if (f[i - j][j] == -1 && f[i - j][j - 1] == -1) {  
16.                 continue;  
17.             }  
18.             if (f[i - j][j] != -1) f[i][j] = f[i - j][j] + 1;  
19.             if (j > 1 && f[i - j][j - 1] != -1) {  
20.                 if (f[i][j] == -1)  
21.                     f[i][j] = f[i - j][j - 1] + 1;  
22.                 else  
23.                     f[i][j] = Math.min(f[i - j][j - 1] + 1, f[i][j]);  
24.             }  
25.             if (i + j + 1 >= len) {  
26.                 ans = Math.min(f[i][j] + 1, ans);  
27.             }  
28.         }  
29.     }  
30.     return ans;  
31. } 

1. int FlogCrossRiver(string river) {  
2.   if (river.empty()) {  
3.     return 0;  
4.   }  
5.   vector<vector<pair<size_t, int>>> vp(river.size());  
6.   vp[0].emplace_back(1, 1);  
7.   int res = INT_MAX;  
8.   for (size_t i = 0; i < vp.size(); ++i) {  
9.     if (river[i] == '0') {  
10.       continue;  
11.     }  
12.     for (auto pr : vp[i]) {  
13.       if (i + pr.first >= vp.size()) {  
14.         res = min(pr.second, res);  
15.       } else if (river[i + pr.first] == '1') {  
16.         vp[i + pr.first].emplace_back(pr.first, pr.second + 1);  
17.       }  
18.       if (i + pr.first + 1 >= vp.size()) {  
19.         res = min(pr.second, res);  
20.       } else if (river[i + pr.first + 1] == '1') {  
21.         vp[i + pr.first + 1].emplace_back(pr.first + 1, pr.second + 1);  
22.       }  
23.     }  
24.   }  
25.   return res;  
26. }  
27. void FlogCrossRiverTest() {  
28.   cout << "11101100t" << FlogCrossRiver("11101100") << endl;  
29.   cout << "11111111t" << FlogCrossRiver("11111111") << endl;  
30.   cout << "11101000t" << FlogCrossRiver("11101000") << endl;  
31.   cout << "11010101t" << FlogCrossRiver("11010101") << endl;  
32. } 

Related: Minimum number of jumps to reach end
Read full article from Least Jumps of Frog Cross River - 我的博客 - ITeye技术网站