题解 | #牛群迁徙#

牛群迁徙

https://www.nowcoder.com/practice/686d79ac54874f5f8abbb83184102873

考察的知识点:动态规划;

解答方法分析:

  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];
    }
};

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务