代码随想录 day39 第九章 动态规划part02

本文主要是介绍代码随想录 day39 第九章 动态规划part02，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

●  62.不同路径

●  63. 不同路径 II

1. 不同路径

关联 leetcode 62. 不同路径 

• 思路

  • 二维矩阵：二维dp数组

  1. dp数组以及下标的含义

     dp[i][j] : 走到 (i,j) 这个位置有多少种不同路径
     

  2. 递推公式

     //机器人只能 向右走 或 向下走
     dp[i][j]=dp[i-1][j]+dp[i][j-1]
     

  3. dp数组如何初始化

     //最上行 和 最左列 一定要初始化
     dp[0][j] , dp[i][0] := 1,1 // 都只有一种走法 
     

  4. 遍历顺序

     1. 从左到右，从上到下

  5. 打印数组

• 题解

  func uniquePaths(m int, n int) int {dp := make([][]int, m)//init the array dpfor i := 0; i < m; i++ {tmp := make([]int, n)dp[i] = tmp}//init first linefor i := 0; i < n; i++ {dp[0][i] = 1}//init first columnfor i := 1; i < m; i++ {dp[i][0] = 1}for i := 1; i < m; i++ {for j := 1; j < n; j++ {dp[i][j] = dp[i-1][j] + dp[i][j-1]}}return dp[m-1][n-1]
  }
  

2. 不同路径 II

关联 leetcode 63. 不同路径 II

• 思路

  1. dp数组以及下标的含义

     dp[i][j] : 走到 (i,j) 这个位置有多少种不同路径
     

  2. 递推公式

     if obs[i][j]==0{ // 没有障碍dp[i][j] = dp[i-1][j] + dp[i][j-1]
     }
     

  3. dp数组如何初始化

     //最上行 和 最左列 一定要初始化
     dp[0][j] , dp[i][0] := 1,1 // 都只有一种走法 
     *遇到障碍后，从障碍开始(包括障碍)后面的 dp[i][j]=0
     

  4. 遍历顺序

     1. 从左到右，从上到下

  5. 打印数组

• 题解

  func uniquePathsWithObstacles(obstacleGrid [][]int) int {x := len(obstacleGrid)y := len(obstacleGrid[0])// 起始位置或者终点位置有障碍，永远到不了if obstacleGrid[0][0] == 1 || obstacleGrid[x-1][y-1] == 1 {return 0}dp := make([][]int, x)//init arrayfor i := 0; i < x; i++ {tmp := make([]int, y)dp[i] = tmp}//init first columnfor i := 0; i < x && obstacleGrid[i][0] == 0; i++ {dp[i][0] = 1}//init first linefor i := 1; i < y && obstacleGrid[0][i] == 0; i++ {dp[0][i] = 1}for i := 1; i < x; i++ {for j := 1; j < y; j++ {if obstacleGrid[i][j] == 0 { //非障碍, 才能计算达到路径dp[i][j] = dp[i-1][j] + dp[i][j-1]}}}return dp[x-1][y-1]
  }
  

这篇关于代码随想录 day39 第九章 动态规划part02的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---