741.摘樱桃.md

741.摘樱桃

/*
 * @lc app=leetcode.cn id=741 lang=typescript
 *
 * [741] 摘樱桃
 */

// @lc code=start
function cherryPickup1(grid: number[][]): number {}
// @lc code=end

解法 1: 枚举第一条路径必经过的点

虽然没法证明这个做法的正确性,但勉强能 AC 掉 😂

function cherryPickup(grid: number[][]): number {
  const n = grid.length
  if (n === 1) return grid[0][0]
  const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(-Infinity))
  dp[0][0] = grid[0][0]

  let dirs = [
    [1, 0],
    [0, 1],
  ]
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === -1 || dp[i][j] === -Infinity) continue
      for (let [di, dj] of dirs) {
        const ni = di + i,
          nj = dj + j
        if (ni < 0 || ni >= n || nj < 0 || nj >= n || grid[ni][nj] === -1) continue
        if (dp[ni][nj] < dp[i][j] + grid[ni][nj]) {
          dp[ni][nj] = dp[i][j] + grid[ni][nj]
        }
      }
    }
  }
  if (dp[n - 1][n - 1] === -Infinity) return 0

  const check = (x: number, y: number, grid: number[][]) => {
    let dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(-Infinity))
    dp[0][0] = grid[0][0]
    const p: [number, number][][] = Array.from({ length: n }, () => new Array(n))
    let dirs = [
      [1, 0],
      [0, 1],
    ]
    for (let i = 0; i <= x; i++) {
      for (let j = 0; j <= y; j++) {
        if (grid[i][j] === -1 || dp[i][j] === -Infinity) continue
        for (let [di, dj] of dirs) {
          const ni = di + i,
            nj = dj + j
          if (ni < 0 || ni > x || nj < 0 || nj > y || grid[ni][nj] === -1) continue
          if (dp[ni][nj] < dp[i][j] + grid[ni][nj]) {
            dp[ni][nj] = dp[i][j] + grid[ni][nj]
            p[ni][nj] = [i, j]
          }
        }
      }
    }
    if (dp[x][y] === -Infinity) return 0
    for (let i = x; i < n; i++) {
      for (let j = y; j < n; j++) {
        if (grid[i][j] === -1 || dp[i][j] === -Infinity) continue
        for (let [di, dj] of dirs) {
          const ni = di + i,
            nj = dj + j
          if (ni < 0 || ni >= n || nj < 0 || nj >= n || grid[ni][nj] === -1) continue
          if (dp[ni][nj] < dp[i][j] + grid[ni][nj]) {
            dp[ni][nj] = dp[i][j] + grid[ni][nj]
            p[ni][nj] = [i, j]
          }
        }
      }
    }
    let res = dp[n - 1][n - 1]

    if (res === -Infinity) return 0
    {
      let cur = [n - 1, n - 1]
      while (cur) {
        const [i, j] = cur
        grid[i][j] = 0
        cur = p[i][j]
      }
    }

    dirs = [
      [-1, 0],
      [0, -1],
    ]
    dp = Array.from({ length: n }, () => new Array(n).fill(-Infinity))
    dp[n - 1][n - 1] = grid[n - 1][n - 1]
    for (let i = n - 1; i >= 0; i--) {
      for (let j = n - 1; j >= 0; j--) {
        if (grid[i][j] === -1 || dp[i][j] === -Infinity) continue
        for (let [di, dj] of dirs) {
          const ni = di + i,
            nj = dj + j
          if (ni < 0 || ni >= n || nj < 0 || nj >= n || grid[ni][nj] === -1) continue
          dp[ni][nj] = Math.max(dp[ni][nj], dp[i][j] + grid[ni][nj])
        }
      }
    }
    res += dp[0][0]
    return res
  }
  let res = 0
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      res = Math.max(
        res,
        check(
          i,
          j,
          grid.map(arr => [...arr]),
        ),
      )
    }
  }
  return res
}

Case

test.each([
  {
    input: {
      grid: [
        [1, 1, 1, 1, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 1],
        [1, 0, 0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 0],
        [0, 0, 0, 1, 1, 1, 1],
      ],
    },
    output: 15,
  },
  {
    input: {
      grid: [
        [0, 1, -1],
        [1, 0, -1],
        [1, 1, 1],
      ],
    },
    output: 5,
  },
  {
    input: {
      grid: [
        [1, 1, -1],
        [1, -1, 1],
        [-1, 1, 1],
      ],
    },
    output: 0,
  },
])('input: grid = $input.grid', ({ input: { grid }, output }) => {
  expect(cherryPickup(grid)).toEqual(output)
})