目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
不同路径 II
访问量:1270
一、简介
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
题目来源:牛客
二、实现
// a[i][j] = a[i][j-1] + a[i-1][j] func uniquePathsWithObstacles(obstacleGrid [][]int) int { if len(obstacleGrid) == 0 || obstacleGrid[0][0] == 1 { return 0 } m := len(obstacleGrid) n := len(obstacleGrid[0]) dp := make(map[int]map[int]int) for i:=0; i< m; i++ { dp[i]= make(map[int]int) } dp[0][0] = 1 // 第一行 for i:=1; i<n; i++ { if obstacleGrid[0][i] == 1 { break } dp[0][i] = 1 } // 第一列 for i :=1; i< m; i++ { if obstacleGrid[i][0] ==1 { break } dp[i][0]= 1 } for i := 1; i < m; i++ { for j := 1; j < n; j++ { if obstacleGrid[i][j] != 1 { dp[i][j] = dp[i-1][j] + dp[i][j-1] } } } return dp[m-1][n-1] }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助