Java 题解 | #牛群迁徙#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param rivers int整型一维数组
     * @return int整型
     */
    public int min_jumps (int[] rivers) {
        // write code here
        int n = rivers.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= rivers[i] && i + j < n; j++) {
                dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
            }
        }
        return dp[n - 1];
    }
}

编程语言是Java。

该题考察的知识点是动态规划，通过使用动态规划来解决最小跳跃次数的问题。

代码的文字解释如下：

• 获取数组的长度，即河流信息的数量，并将其赋值给变量 n。
• 创建一个大小为 n 的整型数组 dp，并将其初始化为最大整数值。
• 将数组 dp 的第一个元素设为 0，表示初始位置的最小跳跃次数为 0。
• 使用两层循环遍历河流信息数组和可能的跳跃步数：外层循环变量 i 表示当前位置。内层循环从 1 到 rivers[i]，表示可以跳跃的步数。检查是否在不超出数组范围的情况下进行跳跃，即 i + j < n。将到达当前位置 i + j 的最小跳跃次数更新为前一位置 i 的最小跳跃次数加 1，并与原先的最小跳跃次数比较取较小值。
• 循环完成后，返回数组 dp 的最后一个元素，表示到达最后位置的最小跳跃次数。