题解 | #牛群迁徙#

知识点

动态规划

思路

设river数组的长度为n

考虑每一个点都可以转移到后续的点，所以我们假设dp[i]代表从下标0走到i所需的最小步数。对于每一个点i，都一步可达[i+1~i+river[i]]的所有点。

所以步数转移方程为min（dp[i+j],dp[i]+1）

遍历每一个点，维护dp数组即可，答案ans=dp[n-1]

代码

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