1937-maximum-number-of-points-with-cost.js

/**
 * @param {number[][]} points
 * @return {number}
 */
const maxPoints = function(points) {
  const m = points.length, n = points[0].length
  let prev = points[0].slice()
  for(let i = 1; i < m; i++) {
    const left = []
    left[0] = prev[0]
    // left to right
    for(let j = 1; j < n; j++) {
      left[j] = Math.max(prev[j], left[j - 1] - 1)
    }
    const right = []
    right[n - 1] = prev[n - 1]
    // right to left
    for(let j = n - 2; j >= 0; j--) {
      right[j] = Math.max(prev[j], right[j + 1] - 1)
    }

    const cur = []
    for(let j = 0; j < n; j++) {
      cur[j] = Math.max(left[j], right[j]) + points[i][j]
    }
    prev = cur
  }

  return Math.max(...prev)
};

// another

/**
 * @param {number[][]} points
 * @return {number}
 */
const maxPoints = function(points) {
    let m = points.length, n = points[0].length;
    let result = 0;
    // dp
    const dp = Array.from({ length: m }, () => Array(n).fill(0));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i == 0) {
                dp[i][j] = points[i][j];
            } else {
                dp[i][j] = Math.max(points[i][j] + dp[i - 1][j], dp[i][j]);
            }
        }
        for (let j = 0; j < n; j++) {
            // right
            for (let k = 1; k < n - j; k++) {
                if (dp[i][j + k] >= dp[i][j] - k) {
                    break;
                }
                dp[i][j + k] = dp[i][j] - k;
            }
            for (let k = 1; k <= j; k++) {
                if (dp[i][j - k] >= dp[i][j] - k) {
                    break;
                }
                dp[i][j - k] = dp[i][j] - k;
            }
        }
    }
    for (let j = 0; j < n; j++) {
        result = Math.max(result, dp[m - 1][j]);
    }
    return result;
};