You are given an integer matrix mat of size m x n and an integer target. Select an integer from each row of the matrix. Your goal is to minimize the absolute difference between the sum of all selected elements and the target value. Returns the smallest absolute difference.

The absolute difference between a and b is the absolute value of a minus b.

Source: LeetCode link: leetcode-cn.com/problems/mi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

It’s a backpack problem. We can let the array f[I][j] represent the presence or absence of the first I row of the matrix, and the state of j

Such as:

  • f[1][1] == trueThat’s the front of the matrix1Rows exist and are1The state of (mat[0][0])
  • f[2][5] == trueThat’s the front of the matrix2Rows exist and are5The state of (mat[0][0] + mat[1][0])
  • .

The absolute difference between target and the result is the smallest

State transition equation: [I] [j] f = f [I] [j] | | f [I – 1] [j w. [k]]

The original code

var minimizeTheDifference = function(mat, Target) {const m = mat.length const n = mat[0]. Length const Max = 4900 Fill (0).map(item => new Array(Max + 1).fill(false)) f[0][0] = true for (let I = 1; i <= m; i ++) { let w = mat[i - 1] for (let k = 0; k < n; k ++) { for (let j = w[k]; j <= max; J + +) {f [I] [j] [I] [j] = f | | f [I - 1] [j w. [k]] / / if f [I] [j] has been to true, }}} let min = 5000 for (let I = 1, abs; i <= max; i ++) { if (f[m][i]) { abs = Math.abs(target - i) if (abs < min) min = abs else return min } } return min };Copy the code

Improve your code

We can simply find that j in the third for loop has gone through too many useless traversals, and f only needs the i-th and i-1 terms, so we can optimize the spatial complexity with scrolling arrays

var minimizeTheDifference = function(mat, target) { const m = mat.length const n = mat[0].length const max = 4900 const f = new Array(2).fill(0).map(item => new Array(max + 1).fill(false)) f[0][0] = true for (let i = 1, r = 0; i <= m; i ++) { let w = mat[i - 1] let cur = i % 2, pre = (i - 1) % 2 f[cur].fill(false) for (let k = 0, newR = r; k <= newR; K ++) {if (f[pre][k]) {for (let j = 0; j < n; j ++) { f[cur][k + w[j]] = true r = Math.max(r, k + w[j]) } } } } let min = 5000 for (let i = 1, abs; i <= max; i ++) { if (f[m % 2][i]) { abs = Math.abs(target - i) if (abs < min) min = abs else return min } } return min };Copy the code