题解 | #牛群迁徙#

大家好，我是阿Q，牛群的迁徙问题让我来解决！

题目考察的知识点

动态规划

题目解答方法的文字分析

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

具体步骤如下：

1. 初始化dp数组为INT_MAX，长度与rivers数组相同。dp[0]表示从初始位置到达初始位置的最小跳跃次数，因为初始位置不需要跳跃，所以dp[0] = 0。
2. 从第一个河流位置开始，依次遍历数组rivers，对于每个位置i，我们遍历从当前位置i向前跳跃的所有可能距离j（0 <= j <= rivers[i]），计算从初始位置到达位置i+j的最小跳跃次数。
3. 更新dp[i+j]为min(dp[i+j], dp[i] + 1)。这里dp[i] + 1表示从初始位置跳到位置i再跳一次到位置i+j。
4. 最后返回dp[n-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; // 初始位置到达初始位置的最小跳跃次数为0

        for (int i = 0; i < n; ++i) {
            // 遍历从当前位置i向前跳跃的所有可能距离j（0 <= j <= rivers[i]）
            for (int j = 1; j <= rivers[i] && i + j < n; ++j) {
                // 更新从初始位置到达位置i+j的最小跳跃次数
                dp[i + j] = min(dp[i + j], dp[i] + 1);
            }
        }

        return dp[n - 1];
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！