当前位置：首页 > article >正文

力扣动态规划-17【算法学习day.111】

article 2025/2/2 13:33:54

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？建议灵神的题单和代码随想录）和记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.统计异或值为给定值的路径数目

题面链接：3393. 统计异或值为给定值的路径数目 - 力扣（LeetCode）

题面:

附上灵神代码:

class Solution {
    private static final int MOD = 1_000_000_007;

    public int countPathsWithXorValue(int[][] grid, int k) {
        int mx = 0;
        for (int[] row : grid) {
            for (int val : row) {
                mx = Math.max(mx, val);
            }
        }
        int u = 1 << (32 - Integer.numberOfLeadingZeros(mx));
        if (k >= u) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;
        int[][][] memo = new int[m][n][u];
        for (int[][] mat : memo) {
            for (int[] row : mat) {
                Arrays.fill(row, -1);
            }
        }
        return dfs(grid, m - 1, n - 1, k, memo);
    }

    private int dfs(int[][] grid, int i, int j, int x, int[][][] memo) {
        if (i < 0 || j < 0) {
            return 0;
        }
        int val = grid[i][j];
        if (i == 0 && j == 0) {
            return x == val ? 1 : 0;
        }
        if (memo[i][j][x] != -1) {
            return memo[i][j][x];
        }
        int left = dfs(grid, i, j - 1, x ^ val, memo);
        int up = dfs(grid, i - 1, j, x ^ val, memo);
        return memo[i][j][x] = (left + up) % MOD;
    }
}