Go语言中值传递dp切片时递归为何能实现更新？

问题1：递归调用中dp切片是如何完成更新的？ #

递归过程是自底向上填充dp缓存：

• 调用path(row, column)时，先判断当前位置是否越界、是障碍、已计算过（dp值不为-1），满足任一条件就直接返回对应结果。
• 若当前位置未计算，会先递归调用下方（row+1, column）和右方（row, column+1）的路径数。这两个递归会先完成自身的计算逻辑，把对应dp位置的结果填充好，再返回数值。
• 将两个递归返回的结果相加，赋值给dp[row][column]，当前位置的路径数就被缓存下来。后续再访问该位置时，直接返回缓存值，无需重复计算。

举个简单流程：从(0,0)开始递归，会先触达右下角(m-1,n-1)，该位置返回1；接着回溯到它的上方和左方，把这两个位置的dp值设为1；继续向上回溯，每个位置都将下方和右方的结果相加后存入自身dp位置，直到回到起点(0,0)。

问题2：为什么值传递的dp切片能被更新？ #

Go语言确实是值传递，但切片本质是一个包含三个字段的结构体：

type slice struct {
    ptr *[]byte  // 指向底层数组的指针
    len int      // 切片长度
    cap int      // 切片容量
}

当把dp切片传入函数时，传递的是这个结构体的副本，但副本里的ptr指针依然指向原始的底层数组。所以在函数中修改dp[row][column]，实际是通过指针修改了底层数组的元素，而main函数中的dp切片也指向同一个底层数组，因此能看到修改后的结果。

简言之：传递的是切片的“描述符”副本，但底层数组是共享的，修改元素会影响所有指向该底层数组的切片。

相关代码 #

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))
}

内容的提问来源于stack exchange，提问作者Deepak Sharma