我们在返回值之后存储该值,在递归调用中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/