Portfolio

문제

You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix.

To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score.

However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score.

Return the maximum number of points you can achieve.

abs(x) is defined as:

x for x >= 0.

x for x < 0.

풀이

은찬

(풀이 참조했습니다..ㅠ)


const maxPoints = (points) => {
    const m = points.length;
    const n = points[0].length;
    const dp = Array.from({length: m}, () => Array(n).fill(-1));
    
    dp[0] = points[0];
    
    for(let i = 1; i < m; i++){
        let left = -Infinity;
        let right = -Infinity;
        
        for(let j = 0; j < n; j++){
            left = Math.max(left, dp[i - 1][j] + j);
            dp[i][j] = Math.max(dp[i][j], points[i][j] - j + left);
        }
        
        for(let j = n - 1; j >= 0; j--){
            right = Math.max(right, dp[i - 1][j] - j);
            dp[i][j] = Math.max(dp[i][j], points[i][j] + j + right);
        }
    }
    
    return dp[m - 1].reduce((prev, current) => prev < current ? current : prev);
};

재영

시간초과


/**
 * @param {number[][]} points
 * @return {number}
 */
var maxPoints = function (points) {
  const row = points.length;
  const col = points[0].length;

  const dp = Array.from({ length: row }, () => new Array(col).fill(0));
  dp[0] = [...points[0]];

  for (let i = 1; i < row; i += 1) {
    for (let j = 0; j < col; j += 1) {
      const now = dp[i][j];
      for (let k = 0; k < col; k += 1) {
        dp[i][j] = Math.max(dp[i - 1][k] - Math.abs(j - k), dp[i][j]);
      }
      dp[i][j] += points[i][j];
    }
  }

  return Math.max(...dp[row - 1]);
};

const points = [
  [1, 2, 3],
  [1, 5, 1],
  [3, 1, 1],
];
console.log(maxPoints(points));

해결 - 최대한 변수를 사용하지 않았더니 풀림.


/**
 * @param {number[][]} points
 * @return {number}
 */
var maxPoints = function (points) {
  const row = points.length;
  const col = points[0].length;
  for (let i = 1; i < row; i += 1) {
    for (let j = 0; j < col; j += 1) {
      let maxValue = 0;
      for (let k = 0; k < col; k += 1) {
        maxValue = Math.max(points[i - 1][k] - Math.abs(j - k), maxValue);
      }
      points[i][j] = maxValue + points[i][j];
    }
  }

  return Math.max(...points[row - 1]);
};

효율성도 제일 낮고... 굉~장히 맘에 안 든다...^^

Maximum Number of Points with Cost

문제

풀이

시간초과

해결 - 최대한 변수를 사용하지 않았더니 풀림.