refactor 312

fishercoder1534 · fishercoder1534 · commit 48017b9cf4be · 2022-01-01T10:34:23.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_312.java b/src/main/java/com/fishercoder/solutions/_312.java
@@ -3,27 +3,39 @@
 public class _312 {
 
     public static class Solution1 {
-        public int maxCoins(int[] iNums) {
-            int[] nums = new int[iNums.length + 2];
+        /**
+         * credit: https://leetcode.com/problems/burst-balloons/discuss/76228/Share-some-analysis-and-explanations
+         * <p>
+         * Divide and conquer with memoization
+         */
+        public int maxCoins(int[] nums) {
+            int[] input = new int[nums.length + 2];
             int n = 1;
-            for (int x : iNums) {
+            for (int x : nums) {
                 if (x > 0) {
-                    nums[n++] = x;
+                    input[n++] = x;
                 }
             }
-            nums[0] = nums[n++] = 1;
+            input[0] = 1;
+            input[n++] = 1;
 
-            int[][] dp = new int[n][n];
-            for (int k = 2; k < n; ++k) {
-                for (int left = 0; left < n - k; ++left) {
-                    int right = left + k;
-                    for (int i = left + 1; i < right; ++i) {
-                        dp[left][right] = Math.max(dp[left][right],
-                                nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
-                    }
-                }
+            int[][] memo = new int[n][n];
+            return burst(memo, input, 0, n - 1);
+        }
+
+        private int burst(int[][] memo, int[] nums, int left, int right) {
+            if (left + 1 == right) {
+                return 0;
+            }
+            if (memo[left][right] > 0) {
+                return memo[left][right];
+            }
+            int ans = 0;
+            for (int i = left + 1; i < right; i++) {
+                ans = Math.max(ans, nums[left] * nums[i] * nums[right] + burst(memo, nums, left, i) + burst(memo, nums, i, right));
             }
-            return dp[0][n - 1];
+            memo[left][right] = ans;
+            return ans;
         }
     }
 }
diff --git a/src/test/java/com/fishercoder/_312Test.java b/src/test/java/com/fishercoder/_312Test.java
@@ -0,0 +1,33 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._312;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _312Test {
+    private static _312.Solution1 solution1;
+    private static int[] nums;
+    private static int expected;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _312.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        nums = new int[]{3, 1, 5, 8};
+        expected = 167;
+        assertEquals(expected, solution1.maxCoins(nums));
+    }
+
+    @Test
+    public void test2() {
+        nums = new int[]{1, 5};
+        expected = 10;
+        assertEquals(expected, solution1.maxCoins(nums));
+    }
+
+}
