初始化 Python 二维列表

先说结论

使用 Python 的列表做二维数组时，初始化应当使用列表推导式或者使用嵌套循环逐行逐个元素添加，不应当使用*运算创建多行列表，使用list * n形式创建的多个行列表的id是相同的，也就是说这些行引用的是内存中的相同地址，修改任何一行的值，其他行都会被修改。

验证代码

使用一个简短的程序对这个问题进行验证，分别使用了列表推导式、*与列表推导式结合、完全使用*三种方式对二维数组初始化。

def print_array(array):
    [print(*row) for row in array]

def init1(rows, cols):
    array = [[0 for _ in range(cols)] for _ in range(rows)]
    return array

def init2(rows, cols):
    array = [[0] * cols for _ in range(rows)]
    return array

def init3(rows, cols):
    array = [[0] * cols] * rows
    return array

if __name__ == "__main__":
    rows = 3  # 行数
    cols = 5  # 列数

    array1 = init1(rows, cols)
    print("\narray1:")
    print_array(array1)
    print(f"row0 id:{id(array1[0])}, row1 id:{id(array1[1])}")
    print(f"row0 id == row1 id ?  {id(array1[0])==id(array1[1])}")

    array2 = init2(rows, cols)
    print("\narray2:")
    print_array(array2)
    print(f"row0 id:{id(array2[0])}, row1 id:{id(array2[1])}")
    print(f"row0 id == row1 id ?  {id(array2[0])==id(array2[1])}")

    array3 = init3(rows, cols)
    print("\narray3:")
    print_array(array3)
    print(f"row0 id:{id(array3[0])}, row1 id:{id(array3[1])}")
    print(f"row0 id == row1 id ?  {id(array3[0])==id(array3[1])}")

程序运行的结果如下

程序运行结果

可以看到在创建行时不能简单地使用*创建多行，这样创建的行的内存地址相同。

这个问题的来源

最近用 Python 做到了 LeetCode 中的一道动规题62.不同路径

思路

按描述，走到某一位置的路径可能有两个来源，一个是当前位置左侧的位置，另一个是当前位置的上侧位置，符合基本的动规思路

动规数组：dp[i][j]表示从起点到坐标 i,j 处的路径数
递推关系：dp[i][j] = dp[i-1][j] + dp[i][j-1]，含义是当前位置的路径数是所有可能的上一步的路径数的加和，可能的上一步即当前位置[i][j]的左侧[i-1][j]或者上侧[i][j-1]
初始化：根据递推关系含义，应当对起始的左侧和上侧进行初始化，也就是对地图的左边界，上边界初始化，每个格子的路径都是 1，因为不可能再有其他方案走到这些位置
遍历顺序：i,j需要两层循环，两层循环都需要顺序遍历，因为递推关系中使用的是当前位置之前的状态值。两层循环的先后顺序可以任意安排，可以从左到右从上到下 (先j后i，i在j之外)，也可以从上到下从左到右 (先i后j，j在i之外)，因为这不影响dp[i][j]总是在dp[i-1][j]和dp[i][j-1]之后计算这一基本要求

代码

def uniquePaths(self, m: int, n: int) -> int:
    # m 行 n 列
    dp = [[0] * n] * m
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    # for j in range(1, n):
    #     for i in range(1, m):
    #         dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[i][j]

当我尝试用注释掉的两层循环来代替程序中先j后i的循环来说明两层循环的次序并不影响结果时，意外的出现了错误。经过调试发现，在经过对边界值进行初始化的两个循环 (for i in range(m)和for j in range(n)) 后，二维数组中出现了错误，此时数组中的所有值全都变成了 1，只不过程序中先j后i的循环，会一次性使用完一整行的元素之后去遍历下一行，恰好避开了这个错误。但是交换循环次序后，逐列遍历会反复在不同行之间修改元素的值，这会导致其他行也被修改，取到错误的数值，得到错误结果。

将创建dp数组的代码修改后两种循环次序均能够得到正确的结果。