_1981.java

packagecom.fishercoder.solutions.secondthousand;

publicclass_1981 {
publicstaticclassSolution1 {
/*
 * creidt: https://leetcode.com/problems/minimize-the-difference-between-target-and-chosen-elements/discuss/1418614/Java-dp-code-with-proper-comments-and-explanation
 */
intans = Integer.MAX_VALUE;
boolean[][] dp;

publicintminimizeTheDifference(int[][] mat, inttarget) {
dp =
newboolean[mat.length]
 [4900]; // we use 4900 due to the contraints in this problem: 70 * 70 =
// 4900
memo(mat, 0, 0, target);
returnans;
 }

privatevoidmemo(int[][] mat, introw, intsum, inttarget) {
if (dp[row][sum]) {
return;
 }
if (row == mat.length - 1) {
for (inti = 0; i < mat[0].length; i++) {
ans = Math.min(ans, Math.abs(sum + mat[row][i] - target));
 }
dp[row][sum] = true;
return;
 }
for (inti = 0; i < mat[0].length; i++) {
memo(mat, row + 1, sum + mat[row][i], target);
 }
dp[row][sum] = true;
 }
 }
}