2021-07-28 华为

第一道题：贪心算法
第二道题：拓扑排序
第三道题：路径和 III

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])

        # 处理：回溯算法
        # 1.找到起始点先
        origin = []

        pathCnt = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 1:
                    origin = [i, j]
                    pathCnt += 1
                elif grid[i][j] == 0:
                    pathCnt += 1

        memo = [[False]*col for i in range(row)]

        ret = self.backTracking(grid, memo, 0, row, col, origin[0], origin[1], 0, pathCnt)
        return ret
    
    def backTracking(self, grid, memo, cnt, row, col, i, j, zeroSum, limit):
        memo = memo.copy()
        # 剪枝
        if i < 0 or i >= row or j < 0 or j >= col or memo[i][j] or grid[i][j] == -1:
            return cnt

        # if grid[i][j] != '0' and grid[i][j] != '1' and grid[i][j] != '2':
        #     return cnt
        # elif grid[i][j] == '0' or grid[i][j] == '1':
        #     grid[i][j] = '-1'

        # 终止条件
        if grid[i][j] == 2 and zeroSum == limit:
            cnt += 1
            return cnt

        # 实际操作
        memo[i][j] = True

        # 递归拆解
        # 上下左右
        cnt = self.backTracking(grid, memo, cnt, row, col, i + 1, j, zeroSum+1, limit)
        cnt = self.backTracking(grid, memo, cnt, row, col, i - 1, j, zeroSum+1, limit)
        cnt = self.backTracking(grid, memo, cnt, row, col, i, j - 1, zeroSum+1, limit)
        cnt = self.backTracking(grid, memo, cnt, row, col, i, j + 1, zeroSum+1, limit)
        # 为什么还要置为False
        memo[i][j] = False

        return cnt

原因：memo.copy()是浅拷贝，特别对于这种路径题目，一定要在递归拆解之后把实际操作的值给变重置回来，所以这句 memo = memo.copy() 是无效的。如果你想完全把memo复制出来，可以使用深复制 copy.deepcopy

from copy import deepcopy

memo = deepcopy(memo)