[Java] Detailed Explanation - DP with Graph Demo
Key Notes:\n- Firstly, you need to know: a ^ b ^ a = b\n- Then: see the graph below:\n\t- dp[i][j] means XOR of from 0 to i and 0 to j\n\t- To calculate dp[i][j
**Key Notes:**\n- Firstly, you need to know: **a ^ b ^ a = b**\n- Then: see the graph below:\n\t- dp[i][j] means XOR of from 0 to i and 0 to j\n\t- To calculate dp[i][j] at point D\n\t- dp[i - 1][j] = (A ^ C), dp[i][j - 1] = (A ^ B)\n\t- **dp[i - 1][j] ^ dp[i][j - 1]** = A ^ C ^ A ^ B = B ^ C\n\t- **dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1]** = B ^ C ^ A\n\t- **dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1] ^ matrix[i][j]** = dp[i][j] is the result we are looking for!\n\n![image](https://assets.leetcode.com/users/images/c4442d53-9ac5-4351-9b72-c31726a91d90_1611461622.9288108.png)\n\n```java\nint M = matrix.length, N = matrix[0].length;\nint[][] dp = new int[M][N];\n\nPriorityQueue<Integer> pq = new PriorityQueue<>();\n\nfor (int i = 0; i < M; ++i) {\n\tfor (int j = 0; j < N; ++j) {\n\n\t\tint x = (i - 1 < 0 ? 0 : dp[i - 1][j]);\n\t\tint y = (j - 1 < 0 ? 0 : dp[i][j - 1]);\n\t\tint z = (i - 1 < 0 || j - 1 < 0 ? 0 : dp[i - 1][j - 1]);\n\n\t\tdp[i][j] = (x ^ y ^ z ^ matrix[i][j]);\n\n\t\tpq.add(dp[i][j]);\n\t\tif (pq.size() > k) pq.poll();\n\t}\n}\n\nreturn pq.poll();\n```\n
[]