Least Jumps of Frog Cross River

Jump River | tech::interview
给一个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，跳出数组范围，成功过河。

DP:
http://yuanhsh.iteye.com/blog/2174295

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. }  

https://sites.google.com/site/codingbughunter/algorithm-question-discuss

    public int jump(int[] river) {
        List<Map<Integer, Integer>> states = new ArrayList<>();
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < river.length; i++) {
            states.add(new HashMap<Integer, Integer>());
        }
        states.get(0).put(1, 0);
        for (int i = 0; i < river.length; i++) {
            for (int speed : states.get(i).keySet()) {
                for (int j = 0; j < 2; j++) {
                    int nextStep = speed + i + j;
                    int step = states.get(i).get(speed) + 1;

                    if (nextStep >= river.length) {
                        min = Math.min(min, step);
                    } else if (river[nextStep] == 1) {
                        states.get(nextStep).put(speed + j, step);
                    }
                }
            }
        }
        return min;
    }

http://kevinhliftlove.blogspot.com/2014/07/problem-of-crossing-river.html

A recursive solution + DP (top-down: memorization of previous solutions)

int minStepsCrossRiver(int[] paths, int pos, int vel, ArrayList<HashMap<Integer, Integer>> A) {
if (pos >= paths.length)
return 0;
if (paths[pos] == 0)
return -1;
if (A.get(pos).containsKey(vel)) {
return A.get(pos).get(vel);
}

int s1 = minStepsCrossRiver(paths, pos+vel, vel, A);
int s2 = minStepsCrossRiver(paths, pos+vel+1, vel+1, A);

int res = 0;
if (s1 < 0 && s2 < 0)
res = -1;
else if (s1 < 0)
res = s2 + 1;
else if (s2 < 0)
res = s1 + 1;
else
res = Math.min(s1, s2)+1;
A.get(pos).put(vel, res);
return res;
    }

    public static void main(String[] args) {
Solution s = new Solution();
int[] paths = {1, 2, 1, 0, 1, 1, 0, 0};
ArrayList<HashMap<Integer, Integer>> A = new ArrayList<HashMap<Integer, Integer>>();
for (int i = 0; i < paths.length; i++) {
A.add(new HashMap<Integer, Integer>());
}
System.out.print(s.minStepsCrossRiver(paths, 0, 1, A));
}
https://github.com/skyyyyy/algorithm/blob/master/cross_river.cpp
//recursive
int crossRiver(int A[], int n, int speed, int index){
    if(index >= n) return 0;
else if(A[index] == 0) return n;
return 1+min(crossRiver(A,n,speed,index+speed), crossRiver(A,n,speed+1,index+speed+1));
}
http://codeanytime.blogspot.com/2014/12/original-post-httpwww.html

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; 
}

int min_river_jumps_dp(const vector<int>& river) {

    if (river.empty()) return 0;



    vector<vector<pair<size_t, int>>> vp(river.size());

    vp[0].emplace_back(1, 1);

   

    int ret = INT_MAX;

    for (auto i = 0; i < vp.size(); ++i) {

        if (!river[i]) continue;

       

        for (auto pr : vp[i]) {

            if (i + pr.first >= vp.size()) {

                ret = min(pr.second, ret);

            } else if (river[i + pr.first]) {

                vp[i + pr.first].emplace_back(pr.first, pr.second + 1);

            }

            if (i + pr.first + 1 >= vp.size()) {

                ret = min(pr.second, ret);

            } else if (river[i + pr.first + 1]) {

                vp[i + pr.first + 1].emplace_back(pr.first + 1, pr.second + 1);

            }

        }

    }

    return ret == INT_MAX ? -1 : ret;

}

Memorized recursive solution

int min_river_jumps(const vector<int>& river) {

    map<pair<int,int>, int> memory;

   

    function<int(int,int)> dfs = [&](int id, int speed) -> int {

        if(id >= river.size()) return 0;

        if(memory.count({id,speed})) return memory[{id,speed}];

       

        int ret = -1;

        if (river[id]) {

            int ret0 = dfs(id + speed, speed);

            int ret1 = dfs(id + speed + 1, speed + 1);

           

            if(ret0 >= 0 && ret1 >= 0) {

                ret = min(ret0,ret1) + 1;

            } else if(ret0 < 0 && ret1 < 0) {

                ret = -1;

            } else {

                ret = max(ret0,ret1) + 1;

            }

        }

        memory[{id,speed}] = ret;

        return ret;

    };   

    return dfs(0, 1);

}

Read full article from Jump River | tech::interview