Create Minimize the Difference Between Target and Chosen Elements [19… (qiyuangong#47)

parascoding · web-flow · commit ecdb28240dfe · 2021-12-05T20:21:59.000+08:00
* Create Minimize the Difference Between Target and Chosen Elements [1981].java Contributed by @parascoding
diff --git a/java/1981_Minimize_the_Difference_Between_Target_and_Chosen_Elements.java b/java/1981_Minimize_the_Difference_Between_Target_and_Chosen_Elements.java
@@ -0,0 +1,28 @@
+class Solution {
+    public int minimizeTheDifference(int[][] a, int k) {
+        n=a.length;
+        m=a[0].length;        
+        min=Integer.MAX_VALUE;
+        dp=new boolean[n][5000];
+        solve(a,k,0,0,0);
+        return min;
+    }
+    private void solve(int a[][],int k,int sum,int row,int col)
+    {
+        if(dp[row][sum]) return;
+        if(n-1==row)
+        {
+            for(int i=0;i<m;i++)
+            min=Math.min(min,Math.abs(k-sum-a[row][i]));
+            dp[row][sum]=true;
+            return;
+        }
+        
+        for(int i=0;i<m;i++)
+            solve(a,k,sum+a[row][i],row+1,col);
+        dp[row][sum]=true;
+    }
+    private int min;
+    private int dy[],n,m;
+    private boolean dp[][];
+}
