LeetCode 1981. Minimize the difference between the target value and the selected element one question per day

Problem description

Give you a size of m x n The integer matrix of mat And an integer target .

From matrix's Every line Select an integer from the , Your goal is   To minimize the   Of all selected elements   and   And target value target Of Absolute difference .

return The smallest absolute difference .

a and b Two digit Absolute difference yes a - b The absolute value of .

Example 1：

Input ：mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
Output ：0
explain ： One possible optimal option is ：
- On the first line, choose 1
- On the second line, choose 5
- On the third line, choose 7
The sum of the selected elements is 13 , Equal to the target value , So the absolute difference is 0 .
Example 2：

Input ：mat = [[1],[2],[3]], target = 100
Output ：94
explain ： The only option is ：
- On the first line, choose 1
- On the second line, choose 2
- On the third line, choose 3
The sum of the selected elements is 6 , The absolute difference is 94 .
Example 3：

Input ：mat = [[1,2,9,8,7]], target = 6
Output ：1
explain ： The best choice is to choose the first line 7 .
The absolute difference is 1 .
 

Tips ：

m == mat.length
n == mat[i].length
1 <= m, n <= 70
1 <= mat[i][j] <= 70
1 <= target <= 800

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/minimize-the-difference-between-target-and-chosen-elements
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Java

class Solution {
    public int minimizeTheDifference(int[][] mat, int target) {
        int n = mat.length;
        // 70 * 70
        boolean[][] dp = new boolean[n][5000];
        // Deal with the first line 
        for(int num : mat[0]) dp[0][num] = true;

        for(int i = 1;i < n;i++){
            // The elements of each line 
            for(int val : mat[i]){
                for(int j = val;j < 5000;j++){
                    // The previous line is optional j-val value , The current line can be selected j
                    dp[i][j] = dp[i][j] || dp[i - 1][j - val];
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        for(int j = 0;j < 5000;j++){
            if(dp[n - 1][j]){
                ans = Math.min(ans,Math.abs(j - target));
            }
        }
        return ans;
    }
}