576.出界的路径数

链接：576.出界的路径数
难度：Medium
标签：动态规划
简介：给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。

题解 1 - typescript

• 编辑时间：2021-08-15
• 执行用时：120ms
• 内存消耗：43.6MB
• 编程语言：typescript
• 解法介绍：dp[i][j][k]=第 i 步时，[j][k]坐标的最大数量。

function findPaths(
  m: number,
  n: number,
  maxMove: number,
  startRow: number,
  startColumn: number
): number {
  const mod = 10 ** 9 + 7;
  const directions: [number, number][] = [
    [0, 1],
    [1, 0],
    [-1, 0],
    [0, -1],
  ];
  const dp = new Array(maxMove + 1)
    .fill(0)
    .map(_ => new Array(m).fill(0).map(_ => new Array(n).fill(0)));
  dp[0][startRow][startColumn] = 1;
  let ans = 0;
  for (let i = 0; i < maxMove; i++) {
    for (let j = 0; j < m; j++) {
      for (let k = 0; k < n; k++) {
        const cnt = dp[i][j][k];
        if (cnt <= 0) continue;
        for (const [moveRow, moveCol] of directions) {
          const row = j + moveRow;
          const col = k + moveCol;
          if (row >= 0 && row < m && col >= 0 && col < n) {
            dp[i + 1][row][col] = (dp[i + 1][row][col] + cnt) % mod;
          } else {
            ans = (ans + cnt) % mod;
          }
        }
      }
    }
  }
  return ans;
}