题解 | #牛群迁徙#

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

一、题目考察的知识点

二、题目解答方法的文字分析

首先初始化dp数组

dp数组的意思是从当前点到初始点最小跳跃次数，用两层循环遍历所有可能，并维护最小跳跃次数

三、本题解析所用的编程语言

c++