我们在返回值之后存储该值，在递归调用中DP如何被更新。
我们传递的代码是传值而不是传引用。
根据我的理解，它应该传递默认值dp，因为我们在main函数中创建了它。
package main
import "fmt"
func path(row, column int, obstacleGrid, dp [][]int) int {
m := len(obstacleGrid)
n := len(obstacleGrid[0])
fmt.Println(row, column, dp)
if row > m-1 || column > n-1 {
return 0
}
if row == m-1 && column == n-1 {
return 1
}
if obstacleGrid[row][column] == 1 {
return 0
}
if dp[row][column] != -1 {
return dp[row][column]
}
dp[row][column] = path(row+1, column, obstacleGrid, dp) + path(row, column+1, obstacleGrid, dp)
return dp[row][column]
}
func main() {
obstacleGrid := [][]int{{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0},
{1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1}, {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0}, {1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1}, {0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}, {1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0}, {0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0},
{1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0}, {1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}}
dp := make([][]int, len(obstacleGrid))
for i := 0; i < len(obstacleGrid); i++ {
temp := make([]int, len(obstacleGrid[0]))
for j := 0; j < len(obstacleGrid[0]); j++ {
temp[j] = -1
}
dp[i] = temp
}
if obstacleGrid[0][0] == 1 {
fmt.Println(0)
return
}
if obstacleGrid[len(obstacleGrid)-1][len(obstacleGrid[0])-1] == 1 {
fmt.Println(0)
return
}
fmt.Println(path(0, 0, obstacleGrid, dp))
}我无法理解dp切片的递归，所有值都应该相同
2条答案
按热度按时间jv2fixgn1#
参见Go Slices: usage and internals。
Go语言中的切片是通过一个“头文件”来实现的，头文件中包含的信息仅够描述切片的内容，这些信息包括切片的长度、切片的容量以及指向切片第0个元素的指针（这个元素以及切片的其他元素都存储在一个 array 中，有时也被称为切片的“后台”或“底层”数组）。
所以当你传递一个切片时，你传递的是这个头，这3个值，而这3个值是你每次传递切片时复制的。数据本身存储在后备数组中，不被复制，你也不希望它被复制（想想传递一个包含MB数据的切片的成本）。
要说明哪些内容正在复制，哪些内容没有复制，可以尝试运行以下示例：
https://go.dev/play/p/MDbPSKcrt1P
6yoyoihd2#
在Golang中，切片在内部是指向实际数组的指针，因此接收函数中的任何更改都会修改实际数组。
事实上，当一个切片被传递时，它是和切片的容量，长度，以及切片的指针（它总是指向底层数组）一起传递的，所以，如果我们在切片中做了一些改变，这些改变通过值传递给函数，将反映在函数外部的切片中。
有关详细说明，请阅读-https://www.geeksforgeeks.org/how-to-pass-a-slice-to-function-in-golang/