题解 | #牛群迁徙#

知识点

动态规划

解题思路

定义一个数组 dp，其中 dp[i] 表示从初始位置到达第 i 个河流所需的最小跳跃次数。初始时将所有dp[i]都定义为无法跳跃，后面遍历更新它。接下来，我们遍历每一个i，对于每个河流 rivers[i]，我们需要找到前面的河流 rivers[j] (0 <= j < i)，使得从 rivers[j] 可以一次跳跃到 rivers[i]。我们可以通过遍历 j 的方式来找到最小的 dp[j]，再加上一次跳跃即可更新 dp[i]。即dp[i] = min(dp[i], dp[j] + 1)。最终，dp[n-1] 就表示从初始位置到达最后一个河流所需的最小跳跃次数。

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 = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (j + rivers[j] >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[n - 1];
    }
}