网站开发要注意的漏洞,公司网站建设定金计入什么科目,地方性门户网站有哪些,wordpress启用摘要失效第九章 动态规划 62.不同路径63.不同路径II代码随想录文章详解总结 62.不同路径
dp[i][j] 表示从(0 ,0)出发到(i, j) 有dp[i][j]的路径数 边界值处理#xff0c;(0 ,0)到(i,0)或(0, j)#xff0c;只有一条路径 对于当前位置#xff0c;只能由左方和上方位置到达#xff0c… 第九章 动态规划 62.不同路径63.不同路径II代码随想录文章详解总结 62.不同路径
dp[i][j] 表示从(0 ,0)出发到(i, j) 有dp[i][j]的路径数 边界值处理(0 ,0)到(i,0)或(0, j)只有一条路径 对于当前位置只能由左方和上方位置到达故有状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]
func uniquePaths(m int, n int) int {dp : make([][]int, m)for i, _ : range dp {dp[i] make([]int, n)}for i : 0; i m; i {for j : 0; j n; j {if i*j 0 {dp[i][j] 1} else {dp[i][j] dp[i-1][j] dp[i][j-1]}}}return dp[m-1][n-1]
}63.不同路径II
若起点或者终点为障碍物直接返回0 边界值处理(0 ,0)到(i,0)或(0, j)若不遇到障碍物只有1条路径若遇到障碍物到达当前位置及之后位置路径数为0。 若遇到障碍物到达当前位置(i, j)的路径数dp[i][j]0否则dp[i][j] dp[i-1][j] dp[i][j-1]
func uniquePathsWithObstacles(obstacleGrid [][]int) int {m, n : len(obstacleGrid), len(obstacleGrid[0])dp : make([][]int, m)if obstacleGrid[0][0] 1 || obstacleGrid[m-1][n-1] 1 {return 0}for i, _ : range dp {dp[i] make([]int, n)}for i : 0; i m obstacleGrid[i][0] 0; i {dp[i][0] 1}for j : 0; j n obstacleGrid[0][j] 0; j {dp[0][j] 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]
}空间优化滑动数组
代码随想录文章详解
62.不同路径 63.不同路径II
总结
今天的题还好哇
