题解 | #牛群迁徙#

• 题目考察的知识点 : 贪心算法，动态规划
• 题目解答方法的文字分析：

1. dp[i] 表示从初始位置到达位置 i 的最小跳跃次数。对于每个位置 i，我们遍历从当前位置向前跳跃的所有可能距离 j（0 <= j <= rivers[i]），更新从初始位置到达位置 i+j 的最小跳跃次数 dp[i+j]。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param rivers int整型一维数组
# @return int整型
#
class Solution:
    def min_jumps(self, rivers: List[int]) -> int:
        n = len(rivers)
        dp = [float('inf')] * n
        dp[0] = 0 # 初始位置到达初始位置的最小跳跃次数为0

        for i in range(n):
            for j in range(1, rivers[i] + 1):
                if i + j < n:
                    dp[i + j] = min(dp[i + j], dp[i] + 1)

        return dp[n - 1]