题解 | #牛群迁徙#

题目考察的知识点是：

贪心算法。

题目解答方法的文字分析：

我们定义一个dp数组，其中dp[i]表示从初始位置到达rivers[i]所需要的最小跳跃次数。我们可以通过迭代数组rivers来填充dp数组，同时计算每一步的最小跳跃次数。

本题解析所用的编程语言：

java语言。

完整且正确的编程代码：

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