Classic Dynamic Programming XII

This type of DP is the one that still doesn't come naturally to me (and yes, I took a look at the hints!). The combination of different XORs along the paths are indeed exponential, but the key is to see that the possible values of the cells are all < 1024. Every XOR then will land somewhere between 0-1023. With that information, we can DP it by using a matrix of DP[rows][cols][1024], and keep track of any path that lights up any of the bits between 0-1023. The cleanness of the code is striking, it is very "symmetrical" when it is set and done, however the mental model is still non-intuitive (IMO) since you're using the values of grid as indexes of the DP. Code is down below, cheers, ACC.

Minimum XOR Path in a Grid - LeetCode

You are given a 2D integer array grid of size m * n.

You start at the top-left cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1).

At each step, you may move either right or down.

The cost of a path is defined as the bitwise XOR of all the values in the cells along that path, including the start and end cells.

Return the minimum possible XOR value among all valid paths from (0, 0) to (m - 1, n - 1).

 

Example 1:

Input: grid = [[1,2],[3,4]]

Output: 6

Explanation:

There are two valid paths:

• (0, 0) → (0, 1) → (1, 1) with XOR: 1 XOR 2 XOR 4 = 7
• (0, 0) → (1, 0) → (1, 1) with XOR: 1 XOR 3 XOR 4 = 6

The minimum XOR value among all valid paths is 6.

Example 2:

Input: grid = [[6,7],[5,8]]

Output: 9

Explanation:

There are two valid paths:

• (0, 0) → (0, 1) → (1, 1) with XOR: 6 XOR 7 XOR 8 = 9
• (0, 0) → (1, 0) → (1, 1) with XOR: 6 XOR 5 XOR 8 = 11

The minimum XOR value among all valid paths is 9.

Example 3:

Input: grid = [[2,7,5]]

Output: 0

Explanation:

There is only one valid path:

• (0, 0) → (0, 1) → (0, 2) with XOR: 2 XOR 7 XOR 5 = 0

The XOR value of this path is 0, which is the minimum possible.

 

Constraints:

• 1 <= m == grid.length <= 1000
• 1 <= n == grid[i].length <= 1000
• m * n <= 1000
• 0 <= grid[i][j] <= 1023​

public class Solution {
    public int MinCost(int[][] grid)
    {
        int[][][] dp = new int[grid.Length][][];
        int MAXVAL = 1024;

        for (int row = 0; row < grid.Length; row++)
        {
            dp[row] = new int[grid[row].Length][];
            for (int col = 0; col < grid[row].Length; col++)
            {
                dp[row][col] = new int[MAXVAL];
            }
        }

        dp[0][0][grid[0][0]] = 1;

        for (int row = 0; row < grid.Length; row++)
        {
            for (int col = 0; col < grid[row].Length; col++)
            {
                if (row == 0 && col == 0) continue;
                for (int x = 0; x < MAXVAL; x++)
                {
                    if ((col > 0 && dp[row][col - 1][x] != 0) || (row > 0 && dp[row - 1][col][x] != 0))
                    {
                        dp[row][col][x ^ grid[row][col]] = 1;
                    }
                }
            }
        }

        for (int x = 0; x < MAXVAL; x++)
        {
            if (dp[dp.Length - 1][dp[dp.Length - 1].Length - 1][x] != 0)
            {
                return x;
            }
        }

        return 0;
    }
}