题解 | #牛群迁徙#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param rivers int整型一维数组
     * @return int整型
     */
    public int min_jumps (int[] rivers) {
        // write code here
        int left = 0;
        int count = 0;
        while (left<rivers.length-1){
            count++;
            if(left+rivers[left]>=rivers.length-1){
                break;
            }
            int index = 0;
            int right = left;
            for(int i=left+1;i<=left+rivers[left] && i<rivers.length;i++){
                if(i+rivers[i]>index){
                    index = i+rivers[i];
                    right = i;
                }
            }
            left = right;
        }
        return count;
    }

}

本题考察的知识点是贪心算法，所用编程语言是java。

我们要求跳到河岸的步数最小，按照贪心的想法我们应该每一步都跳到最大值才能够步数最小。那么接下来我们应该想一想如何做到每一步都跳到最大值，我们每一步的选择只能是当前位置能跳的距离之内，我们应该选择下一步位置加上下一步位置能够跳的距离最大值