当我们通过值传递而不是引用传递时，切片 dp 是如何更新的？

huangapple
go评论132阅读模式
英文:

how the slice dp is getting updated as we are passing it by value not by referebce

问题

我们在递归调用中存储返回后的值，但是我不明白在递归调用中dp是如何更新的。

我们将代码按值传递而不是按引用传递。

根据我的理解，它应该将dp的默认值作为我们在主函数中创建的值传递。

  1. package main
  3. import "fmt"
  5. func path(row, column int, obstacleGrid, dp [][]int) int {
  6. 	m := len(obstacleGrid)
  7. 	n := len(obstacleGrid[0])
  9. 	fmt.Println(row, column, dp)
  11. 	if row > m-1 || column > n-1 {
  12. 		return 0
  13. 	}
  14. 	if row == m-1 && column == n-1 {
  15. 		return 1
  16. 	}
  17. 	if obstacleGrid[row][column] == 1 {
  18. 		return 0
  19. 	}
  20. 	if dp[row][column] != -1 {
  21. 		return dp[row][column]
  22. 	}
  24. 	dp[row][column] = path(row+1, column, obstacleGrid, dp) + path(row, column+1, obstacleGrid, dp)
  25. 	return dp[row][column]
  26. }
  28. func main() {
  29. 	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},
  30. 		{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},
  31. 		{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},
  32. 		{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},
  33. 		{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},
  34. 		{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},
  35. 		{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},
  36. 		{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},
  37. 		{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},
  38. 		{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},
  39. 		{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},
  40. 		{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},
  41. 		{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},
  42. 		{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},
  43. 		{1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}}
  45. 	dp := make([][]int, len(obstacleGrid))
  46. 	for i := 0; i < len(obstacleGrid); i++ {
  47. 		temp := make([]int, len(obstacleGrid[0]))
  48. 		for j := 0; j < len(obstacleGrid[0]); j++ {
  49. 			temp[j] = -1
  50. 		}
  51. 		dp[i] = temp
  52. 	}
  53. 	if obstacleGrid[0][0] == 1 {
  54. 		fmt.Println(0)
  55. 		return
  56. 	}
  57. 	if obstacleGrid[len(obstacleGrid)-1][len(obstacleGrid[0])-1] == 1 {
  58. 		fmt.Println(0)
  59. 		return
  60. 	}
  61. 	fmt.Println(path(0, 0, obstacleGrid, dp))
  62. }

我无法理解dp切片的递归，所有的值应该是相同的。

英文:

we are storing the value after it is returned how in recursion call dp is getting updated.

we are passing the code as pass by value not by reference.

from my understanding it should pass the default value of dp as we created that in main function.

  1. package main
  2. import &quot;fmt&quot;
  3. func path(row, column int, obstacleGrid, dp [][]int) int {
  4. m := len(obstacleGrid)
  5. n := len(obstacleGrid[0])
  6. fmt.Println(row, column, dp)
  7. if row &gt; m-1 || column &gt; n-1 {
  8. return 0
  9. }
  10. if row == m-1 &amp;&amp; column == n-1 {
  11. return 1
  12. }
  13. if obstacleGrid[row][column] == 1 {
  14. return 0
  15. }
  16. if dp[row][column] != -1 {
  17. return dp[row][column]
  18. }
  19. dp[row][column] = path(row+1, column, obstacleGrid, dp) + path(row, column+1, obstacleGrid, dp)
  20. return dp[row][column]
  21. }
  22. func main() {
  23. 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},
  24. {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},
  25. {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},
  26. {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},
  27. {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},
  28. {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},
  29. {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},
  30. {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},
  31. {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},
  32. {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},
  33. {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},
  34. {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},
  35. {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},
  36. {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},
  37. {1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}}
  38. dp := make([][]int, len(obstacleGrid))
  39. for i := 0; i &lt; len(obstacleGrid); i++ {
  40. temp := make([]int, len(obstacleGrid[0]))
  41. for j := 0; j &lt; len(obstacleGrid[0]); j++ {
  42. temp[j] = -1
  43. }
  44. dp[i] = temp
  45. }
  46. if obstacleGrid[0][0] == 1 {
  47. fmt.Println(0)
  48. return
  49. }
  50. if obstacleGrid[len(obstacleGrid)-1][len(obstacleGrid[0])-1] == 1 {
  51. fmt.Println(0)
  52. return
  53. }
  54. fmt.Println(path(0, 0, obstacleGrid, dp))
  55. }

I am not able to understand the recursion for dp slice all the value should be same

答案1

得分: 1

请注意，我将为您翻译以下内容：

参见Go Slices: usage and internals。

在Go语言中，切片是使用一个“头部”来实现的，该头部包含足够的信息来描述切片的内容。这些信息包括切片的长度、切片的容量以及指向切片第一个元素的指针（切片的其余元素也存储在一个数组中，有时称为切片的“后备”或“底层”数组）。

因此，当您传递一个切片时，实际上是传递了这个头部，也就是这三个值，每次传递切片时都会复制这三个值。实际的数据，也就是存储在后备数组中的数据，并不会被复制，也不应该被复制（想想传递包含几兆字节数据的切片会带来多大的开销）。

为了说明什么被复制了，什么没有被复制，您可以尝试运行以下示例：

  1. func set0(s []string, e string) {
  2. 	fmt.Printf("s=%p s[0]=%p\n", &s, &s[0])
  3. 	s[0] = e
  4. }
  6. func main() {
  7. 	a := []string{"foo"}
  8. 	fmt.Printf("a=%p a[0]=%p\n", &a, &a[0])
  9. 	set0(a, "bar")
  11. 	b := a
  12. 	fmt.Printf("b=%p b[0]=%p\n", &b, &b[0])
  13. 	set0(b, "baz")
  15. 	c := b
  16. 	fmt.Printf("c=%p c[0]=%p\n", &c, &c[0])
  17. 	set0(c, "quux")
  19. 	fmt.Println(a, b, c)
  20. }
  22. // 输出：
  23. // a=0xc000010030 a[0]=0xc000014270
  24. // s=0xc000010048 s[0]=0xc000014270
  25. // b=0xc000010060 b[0]=0xc000014270
  26. // s=0xc000010078 s[0]=0xc000014270
  27. // c=0xc000010090 c[0]=0xc000014270
  28. // s=0xc0000100a8 s[0]=0xc000014270
  29. // [quux] [quux] [quux]

链接：https://go.dev/play/p/MDbPSKcrt1P

英文:

See Go Slices: usage and internals.

Slices in Go are implemented using a "header" that contains just enough information to describe the slice's contents. That information is the length of the slice, the capacity of the slice, and a pointer to the 0th element of the slice (this element as well as the rest of the slice's elements are stored in an array, sometimes referred to as the "backing", or "underlying", array of the slice).

So when you pass around a slice, you are passing around this header, these 3 values, and it is these three values that are copied every time you pass around the slice. The data itself, which is stored in the backing array, is not copied, nor would you want it to be copied (just think about what it would cost to pass around a slice containing MBs of data).

To illustrate what's being copied and what's not, you can try running the following example:

  1. func set0(s []string, e string) {
  2. 	fmt.Printf(&quot;s=%p s[0]=%p\n&quot;, &amp;s, &amp;s[0])
  3. 	s[0] = e
  4. }
  6. func main() {
  7. 	a := []string{&quot;foo&quot;}
  8. 	fmt.Printf(&quot;a=%p a[0]=%p\n&quot;, &amp;a, &amp;a[0])
  9. 	set0(a, &quot;bar&quot;)
  11. 	b := a
  12. 	fmt.Printf(&quot;b=%p b[0]=%p\n&quot;, &amp;b, &amp;b[0])
  13. 	set0(b, &quot;baz&quot;)
  15. 	c := b
  16. 	fmt.Printf(&quot;c=%p c[0]=%p\n&quot;, &amp;c, &amp;c[0])
  17. 	set0(c, &quot;quux&quot;)
  19. 	fmt.Println(a, b, c)
  20. }
  22. // output:
  23. // a=0xc000010030 a[0]=0xc000014270
  24. // s=0xc000010048 s[0]=0xc000014270
  25. // b=0xc000010060 b[0]=0xc000014270
  26. // s=0xc000010078 s[0]=0xc000014270
  27. // c=0xc000010090 c[0]=0xc000014270
  28. // s=0xc0000100a8 s[0]=0xc000014270
  29. // [quux] [quux] [quux]

https://go.dev/play/p/MDbPSKcrt1P

答案2

得分: 0

在Golang中，切片（slices）在内部是指向实际数组的指针，因此在接收函数中对切片的任何更改都会修改实际数组。

实际上，当传递一个切片时，它会带有切片的容量、长度和切片的指针（始终指向底层数组）。因此，如果我们对通过值传递给函数的切片进行了一些更改，这些更改将反映在函数外部的切片中。

要进一步了解，请阅读- https://www.geeksforgeeks.org/how-to-pass-a-slice-to-function-in-golang/

英文:

In Golang, slices are internally a pointer to the actual array, so any changes in the receiving function modify the actual array.

Infact when a slice is passed, it is passed with the slice capacity, length, and the pointer of the slice ( which is always pointing to the underlying array). So, if we made some change in the slice which is passed to the function by value will reflect in the slice present outside the function.

For further clarification you can read - https://www.geeksforgeeks.org/how-to-pass-a-slice-to-function-in-golang/

huangapple
  • 本文由 发表于 2023年3月19日 19:12:55
  • 转载请务必保留本文链接：https://go.coder-hub.com/75781573.html
  • dynamic-programming
  • go
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定