题解 | #挤奶路径#

挤奶路径

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

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

解答方法分析:

  1. 定义一个二维数组dp,其中dp[i][j]表示从起点到达位置(i, j)的不同路径数目。
  2. 初始化dp数组。由于只能向下或向右移动,所以第一行和第一列的位置只能从左方或上方到达,因此,如果某个位置有障碍物或者其左方或上方有障碍物,则该位置的路径数为0,否则为1。
  3. 使用动态规划的思想来递推整个dp数组。对于位置(i, j),从左方和上方到达,到达位置(i, j)的路径数等于到达其左方位置(i-1, j)的路径数加上到达其上方位置(i, j-1)的路径数,即dp[i][j] = dp[i-1][j] + dp[i][j-1]。但是如果位置(i, j)有障碍物,则路径数为0,即dp[i][j] = 0。
  4. 返回结果dp[m-1][n-1]。

所用编程语言:C++;

完整编程代码:↓

class Solution {
  public:
    int uniquePathsWithObstacles(vector<vector<int> >& cows) {
        int m = cows.size();
        int n = cows[0].size();
        vector<vector<int> > dp(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            if (cows[i][0] == 1) {
                break;
            }
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            if (cows[0][j] == 1) {
                break;
            }
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (cows[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

全部评论

相关推荐

07-28 16:10
门头沟学院 Java
连笔试都没有就直接挂了&nbsp;这是学历厂吗两段大厂实习一段中厂一点机会都没有吗真的很难绷
xiaolihuam...:校招挂了,然后反手给我捞了个社招
投递虾皮信息等公司10个岗位
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-23 14:18
点赞 评论 收藏
分享
白火同学:先说结论,准大三不是特别好找实习,boss沟通300+没有实习是很正常的情况。一是暑期实习时间太短了,二是在这么多准大四都找不到实习,从实习时间和掌握技术层面,企业会优先看他们。 再说简历,其实985本+准大三到这水平的简历也很优秀了,要说的话,项目经历可以再优化一下,可以基本围绕采取STAR原则,分为项目概述、技术架构、技术亮点、实现结果,再发给AI润色一下。 最后说操作,准大三的话,如果想找实习那就多投,不过现在也7月中旬了,时间上已经略晚了。如果7月底实在找不到,也可以多刷点算法,多学点技术,这实习也不至于一定得有,当然有更好。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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