Leetcode | Maximum Compatibility Score Sum | Java

devstromo · devstromo · commit b36e40445311 · 2025-04-27T22:47:32.000-03:00
diff --git a/leetcode/src/main/java/com/devstromo/medium/p1947/Solution.java b/leetcode/src/main/java/com/devstromo/medium/p1947/Solution.java
@@ -36,4 +36,35 @@ public int maxCompatibilitySum(int[][] students, int[][] mentors) {
 
         return dp[(1 << m) - 1];
     }
+
+    public int maxCompatibilitySumBest(int[][] students, int[][] mentors) {
+        int m = students.length;
+        Integer[] dp = new Integer[(1 << m) + 1];
+        return helper(students, mentors, 0, 0, dp);
+    }
+
+    private int find(int[] arr, int[] brr) {
+        int res = 0;
+        for (int i = 0; i < arr.length; i++) {
+            res += (1 - (arr[i] ^ brr[i]));
+        }
+        return res;
+    }
+
+    private int helper(int[][] students, int[][] mentors, int mask, int index, Integer[] dp) {
+        int m = students.length;
+        int n = students[0].length;
+        if (index == m)
+            return 0;
+        int res = 0;
+        if (dp[mask] != null)
+            return dp[mask];
+        for (int i = 0; i < m; i++) {
+            if (((mask >> i) & 1) == 0)
+                res = Math.max(find(students[index], mentors[i]) + helper(students, mentors, mask | (1 << i), index + 1, dp), res);
+        }
+        return dp[mask] = res;
+    }
+
+
 }
diff --git a/leetcode/src/test/java/com/devstromo/medium/p1947/SolutionUnitTest.java b/leetcode/src/test/java/com/devstromo/medium/p1947/SolutionUnitTest.java
@@ -36,4 +36,33 @@ void testMaximumCompatibilityScoreSum() {
                 }
         ));
     }
+
+    @Test
+    @DisplayName("Test Maximum Compatibility Score Sum Best")
+    void testMaximumCompatibilityScoreSumBest() {
+        assertEquals(8, solution.maxCompatibilitySumBest(
+                new int[][]{
+                        {1, 1, 0},
+                        {1, 0, 1},
+                        {0, 0, 1}
+                },
+                new int[][]{
+                        {1, 0, 0},
+                        {0, 0, 1},
+                        {1, 1, 0}
+                }
+        ));
+        assertEquals(0, solution.maxCompatibilitySumBest(
+                new int[][]{
+                        {0, 0},
+                        {0, 0},
+                        {0, 0},
+                },
+                new int[][]{
+                        {1, 1},
+                        {1, 1},
+                        {1, 1},
+                }
+        ));
+    }
 }
