示例
二维矩阵问题
题目要求：
一个二维矩阵，矩阵的元素是数
- 1.求矩阵从左上角到右下角的路径数目
- 2.矩阵的元素只有0和1求从左上角到右下角的路径数目，0通过，1不通过
- 3.求矩阵从左上角到右下角的最小路径和
思路：
- 1.定义一个二维矩阵dp，dp[i][j]表示nums[i][j]中到此位置的路径数，dp[0][0]=1，第一行或第一列的路径数都是1，此外的其他位置的路径数是其左边和上边的路径数的和，dp[i][j]=dp[i-1][j]+dp[i][j-1]。
- 2.与题目一的思路相似，只是矩阵中只有0和1，遇到0处理方法和问题1相同，遇到1则路径数为0。
- 3.定义一个二维矩阵dp，dp[i][j]表示到此位置的最小路径和。第一行或第一列，dp[i][j]是num[i][j]和dp中左边和上边的路径和中较小数的和，即dp[i][j]=Min(nums[i][j]+dp[i][j-1], nums[i][j]+dp[i-1][j])。
代码(Go)：
package main
import (
"fmt"
"math"
)
//题目1
func UniquePath1(nums [][]int) int {
m := len(nums)
n := len(nums[0])
if nums[0][0] == 1 || nums[m-1][n-1] == 1 {
return 0
}
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
dp[0][0] = 1
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if i == 0 && j > 0 {
dp[i][j] = dp[i][j-1]
continue
}
if j == 0 && i > 0 {
dp[i][j] = dp[i-1][j]
continue
}
if i != 0 && j != 0 {
dp[i][j] = dp[i][j-1] + dp[i-1][j]
}
}
}
return dp[m-1][n-1]
}
//题目2
func UniquePath2(nums [][]int) int {
m := len(nums)
n := len(nums[0])
if nums[0][0] == 1 || nums[m-1][n-1] == 1 {
return 0
}
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
dp[0][0] = 1
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if i == 0 && j > 0 {
dp[i][j] = dp[i][j-1]
continue
}
if j == 0 && i > 0 {
dp[i][j] = dp[i-1][j]
continue
}
if i != 0 && j != 0 {
dp[i][j] = dp[i][j-1] + dp[i-1][j]
}
if nums[i][j] == 1 {
dp[i][j] = 0
}
}
}
return dp[m-1][n-1]
}
//题目3
func MinPathNum(nums [][]int) int {
m := len(nums)
n := len(nums[0])
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
dp[0][0] = nums[0][0]
for i := 1; i < m; i++ {
dp[i][0] = nums[i][0] + dp[i-1][0]
}
for j := 1; j < n; j++ {
dp[0][j] = nums[0][j] + dp[0][j-1]
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
tmp := math.Min(float64(nums[i][j]+dp[i][j-1]), float64(nums[i][j]+dp[i-1][j]))
dp[i][j] = int(tmp)
}
}
return dp[m-1][n-1]
}
func main() {
nums := [][]int{
{0, 0, 0, 0},
{0, 1, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
}
fmt.Println(UniquePath1(nums))
fmt.Println(UniquePath2(nums))
nums1 := [][]int{
{2, 4, 3, 7},
{5, 3, 2, 1},
{4, 8, 6, 2},
}
fmt.Println(MinPathNum(nums1))
}
