题解 | #牛群迁徙#

考察的知识点：动态规划；

解答方法分析：

1. 定义一个数组dp，dp[i]表示到达第i个河流所需要的最小跳跃次数。
2. 初始状态下，dp[0]为0，因为初始位置已经在第一个河流处。
3. 从第一个河流开始，遍历rivers数组。对于第i个河流，需要找到前面的所有河流中能够跳跃到当前河流的最小跳跃次数。因此，遍历从0到i-1的所有河流，找到能够跳跃到当前河流的索引j，并更新dp[i]为dp[j]+1。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param rivers int整型vector
     * @return int整型
     */
    int min_jumps(vector<int>& rivers) {
        int n = rivers.size();
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (j + rivers[j] >= i) {
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[n - 1];
    }
};