题解 | #挤奶路径#

挤奶路径

https://www.nowcoder.com/practice/6ab56cedae0646e19fb64b8bdbad82a6

知识点

动态规划

解题思路

定义一个二维数组dp,dp[i][j]表示从农场的左上角到达位置(i, j)的不同路径数。

首先,我们初始化dp数组。如果农场的左上角有障碍物(即cows[0][0]为1),则路径数为0;否则,路径数为1,即dp[0][0] = 1。

然后,我们根据动态规划的递推关系式来更新dp数组。对于位置(i, j),如果当前位置为障碍物,则路径数为0,即dp[i][j] = 0。否则,可以根据上方位置和左方位置的路径数来计算当前位置的路径数,即dp[i][j] = dp[i-1][j] + dp[i][j-1]。

最后的dp[m-1][n-1]就是最终ans。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param cows int整型二维数组
     * @return int整型
     */
    public int uniquePathsWithObstacles (int[][] cows) {
        // write code here
        int m = cows.length;
        int n = cows[0].length;

        int[][] dp = new int[m][n];

        // 初始化第一个位置
        if (cows[0][0] == 0) {
            dp[0][0] = 1;
        } else {
            dp[0][0] = 0;
        }

        // 初始化第一列
        for (int i = 1; i < m; i++) {
            if (cows[i][0] == 0) {
                dp[i][0] = dp[i - 1][0];
            } else {
                dp[i][0] = 0;
            }
        }

        // 初始化第一行
        for (int j = 1; j < n; j++) {
            if (cows[0][j] == 0) {
                dp[0][j] = dp[0][j - 1];
            } else {
                dp[0][j] = 0;
            }
        }

        // 更新dp数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (cows[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                } else {
                    dp[i][j] = 0;
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}

全部评论

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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