【Leetcode Daily】3393统计异或值为给定值的路径数目

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个二维数组，求从左上角到右下角，同时其中值异或值为目标值 k 的目标路径数目。

思路分享

• 划分子问题，把最后一个值异或 k 得出新的值 q，然后就变成了更小的二维数组的路径目标值为 q。然后得出状态转移方程，f[i+1][j+1][val]=f[i][j+1][val^grid[i][j]] + f[i+1][j][val^grid[i][j]]

  https://leetcode.cn/problems/count-paths-with-the-given-xor-value/solutions/3026905/wang-ge-tu-dpcong-ji-yi-hua-sou-suo-dao-k1bpm/

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def countPathsWithXorValue(self, grid: List[List[int]], k: int) -> int:
        # 递推
        MOD = 1_000_000_007
        m, n = len(grid), len(grid[0])
        u = 1 << max(map(max, grid)).bit_length()
        if k >= u:
            return 0
        f = [[[0] * u for _ in range(n+1)] for _ in range(m+1)]
        f[1][0][0] = 1
        for i in range(m):
            for j in range(n):
                for x in range(u):
                    # print(i, j, x)
                    f[i+1][j+1][x] = (f[i][j+1][x ^ grid[i][j]] + f[i+1][j][x ^ grid[i][j]]) % MOD
        return f[m][n][k]
        # 记忆化搜索
        # m, n = len(grid), len(grid[0])
        # @cache
        # def dfs(i:int, j:int, val:int) -> int:
        #     if i < 0 or j < 0:
        #         return 0
        #     if i == 0 and j == 0:
        #         return 1 if val == grid[0][0] else 0
        #     val ^= grid[i][j]
        #     return (dfs(i-1, j, val) + dfs(i, j-1, val)) % 1_000_000_007
        # return dfs(m-1, n-1, k) % 1_000_000_007