题解 | #牛群迁徙#

牛群迁徙

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

知识点

动态规划

解题思路

定义一个数组 dp,其中 dp[i] 表示从初始位置到达第 i 个河流所需的最小跳跃次数。初始时将所有dp[i]都定义为无法跳跃,后面遍历更新它。接下来,我们遍历每一个i,对于每个河流 rivers[i],我们需要找到前面的河流 rivers[j] (0 <= j < i),使得从 rivers[j] 可以一次跳跃到 rivers[i]。我们可以通过遍历 j 的方式来找到最小的 dp[j],再加上一次跳跃即可更新 dp[i]。即dp[i] = min(dp[i], dp[j] + 1)。最终,dp[n-1] 就表示从初始位置到达最后一个河流所需的最小跳跃次数。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param rivers int整型一维数组
     * @return int整型
     */
    public int min_jumps (int[] rivers) {
        // write code here
        int n = rivers.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (j + rivers[j] >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[n - 1];
    }
}

全部评论

相关推荐

07-22 13:50
门头沟学院 Java
仁者伍敌:其实能找到就很好了,当然收支能抵
点赞 评论 收藏
分享
写不来代码的小黑:这么小的城市能有做it的公司也不容易
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-24 13:39
在记录秋招的大魔王很...:别被忽悠了,我做了多年销售。我可以告诉你,这就是忽悠你的,销售一定要看底薪也要看提成两者不可缺一。提成是有业绩的时候才拿的到的,谁能保证一直有单状态都好。销售有时候很讲究运气的。底薪是你这个人这个岗位日常工作体现的价值。别小看底薪,你看那些跳槽去做经理主管的,底薪底一些,人家愿意去吗?所以那些说销售靠提成的纯属忽悠,除非他们的业务很容易成单。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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