Least Jumps of Frog Cross River

Question:

跳河问题。给一个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

 

Solution 1:

int FlogCrossRiver(string river) {
  if (river.empty()) {
    return 0;
  }
  vector<vector<pair<size_t, int>>> vp(river.size());
  vp[0].emplace_back(1, 1);
  int res = INT_MAX;
  for (size_t i = 0; i < vp.size(); ++i) {
    if (river[i] == '0') {
      continue;
    }
    for (auto pr : vp[i]) {
      if (i + pr.first >= vp.size()) {
        res = min(pr.second, res);
      } else if (river[i + pr.first] == '1') {
        vp[i + pr.first].emplace_back(pr.first, pr.second + 1);
      }
      if (i + pr.first + 1 >= vp.size()) {
        res = min(pr.second, res);
      } else if (river[i + pr.first + 1] == '1') {
        vp[i + pr.first + 1].emplace_back(pr.first + 1, pr.second + 1);
      }
    }
  }
  return res;
}
void FlogCrossRiverTest() {
  cout << "11101100t" << FlogCrossRiver("11101100") << endl;
  cout << "11111111t" << FlogCrossRiver("11111111") << endl;
  cout << "11101000t" << FlogCrossRiver("11101000") << endl;
  cout << "11010101t" << FlogCrossRiver("11010101") << endl;
}

 

Solution2:

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))

 

public int minFrogJumps(int[] a) {
	int len = a.length;
	int[][] f = new int[len][(int)Math.sqrt(len * 2) + 1];
	int ans = Integer.MAX_VALUE;
	for (int i = 1; i < len; i++) {
		Arrays.fill(f[i], -1);
		if (a[i] == 0)  {
			continue;
		}
		for (int j = 1; j <= (int)Math.sqrt(i * 2); j++) {
			if (a[i - j] == 0) {
				f[i][j] = -1;
				continue;
			}
			if (f[i - j][j] == -1 && f[i - j][j - 1] == -1) {
				continue;
			}
			if (f[i - j][j] != -1) f[i][j] = f[i - j][j] + 1;
			if (j > 1 && f[i - j][j - 1] != -1) {
				if (f[i][j] == -1)
					f[i][j] = f[i - j][j - 1] + 1;
				else
					f[i][j] = Math.min(f[i - j][j - 1] + 1, f[i][j]);
			}
			if (i + j + 1 >= len) {
				ans = Math.min(f[i][j] + 1, ans);
			}
		}
	}
	return ans;
}