Minimum stops to cross river

Original Post: http://www.mitbbs.com/article_t/JobHunting/32716569.html
跳河问题。给一个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，跳出数组范围，成功过河。

 
发信人: vinkyqy (Vinky), 信区: JobHunting
标  题: Re: f家店面题
发信站: BBS 未名空间站 (Tue Jun 17 01:01:35 2014, 美东)

for speed in [max_speed ... 1]
  for index in [length-1 ... 0]
      if R==0
          ways[speed][index] = Integer.MAX
      else
         if speed+index>length-1
             ways[speed][inde] = 1
        else
             ways[speed][index] += min(ways[speed][index+speed], ways[speed+
1][index+speed])


return min(ways[1][0], ways[2][0]);

 
发信人: flowerrabbit (花兔大爆发), 信区: JobHunting
标  题: Re: f家店面题
发信站: BBS 未名空间站 (Sun Dec 21 16:45:00 2014, 美东)

int FlogCrossRiver(string river) {
  if (river.empty()) {
    return 0;
  }
  vector>> 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;
}

 
发信人: luckier80 (Luckier), 信区: JobHunting
标  题: Re: f家店面题
发信站: BBS 未名空间站 (Sun Dec 21 19:23:16 2014, 美东)

A recursive solution

public int solve(int[] R) {
     return solve(R, 0, 1, 0); 
}

public int solve(int[] R, int offset, int speed, int stepsTaken) {
     if(offset + speed + 1 >= R.length) return stepsTaken + 1; 
     int minSteps = Integer.MAX_VALUE; 
     if(R[offset + speed] == 1) 
             minSteps = Math.min(minSteps, solve(R, offset + speed, speed, 
stepsTaken + 1)); 
     if(R[offset + speed + 1] == 1) 
             minSteps = Math.min(minSteps, solve(R, offset + speed + 1, 
speed + 1, stepsTaken + 1)); 
     return minSteps; 
}

 
发信人: flowerrabbit (花兔大爆发), 信区: JobHunting
标  题: Re: f家店面题
发信站: BBS 未名空间站 (Sun Dec 21 16:45:00 2014, 美东)

dp[i][j]: 以速度 j 走到第 i 个位置的最少步数
dp[i][j] = min(dp[i-j][j], dp[i-j][j-1])+1 
ans = min(dp[i][j], where i+j+1>=n) + 1