代码随想录 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 dp
  	for i := 0; i < m; i++ {
  		tmp := make([]int, n)
  		dp[i] = tmp
  	}
  	//init first line
  	for i := 0; i < n; i++ {
  		dp[0][i] = 1
  	}
  	//init first column
  	for 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 array
  	for i := 0; i < x; i++ {
  		tmp := make([]int, y)
  		dp[i] = tmp
  	}
  	//init first column
  	for i := 0; i < x && obstacleGrid[i][0] == 0; i++ {
  		dp[i][0] = 1
  	}
  	//init first line
  	for 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]
  }