记录一下最近在 LeetCode 刷的几道动态规划算法题

Divisor Game

题目来源

链接：https://leetcode.com/problems/divisor-game/

难度：easy

题目描述

给定一个数 N，A、B 两个人轮流取数 x，只能取 (0,N) 之间且为 N 的约数（N 对其求余等于 0），并且取完之后剩余的数为 N-x，从剩余数里面继续取，直到一方没法取值为止，另一方获胜。求给定一个数字 N，问先手的 Alice 是否一定可以获胜。

可以简单举几个例子帮助理解题目：A 先手

N === 0 时，先手的一定输，结果为 false

N === 1 时，先手的也没法选，结果为 false

N === 2 时，先手的只能选择 1，后手输，结果为 true

N === 3 时，先手的只能选择 1，选完以后 N === 2，后手胜，结果为 false

N === 4 时，先手可以选择 1 也可以选择 2

如果选 1，剩 3，相当于问，当 N===3 且 B 先手时，A 是否能赢，前面推出 N === 3 且 A 先手时，A 输，所以当 N===3 且 B 先手时，A 能赢
如果选 2，剩 2，由前面 N === 2 的结论知，A 会输
如果 A 先手，A 有先手选择权，所以当 N === 4 时，结果为 true

代码和说明

// dp[i] 即：当 A 先手且当前剩余数为 i 时，A 是否一定赢
// basecase 为 N === 0/1/2 的情形
// 状态转移方程：dp[i] = { dp[m] || dp[n]...|i%m===0,i%n===0}，所有约数 dp 子项求或运算

const divisorGame = function (N) {
  // N === 0/1/2
  const dp = [false, false, true];
  for (let i = 1; i <= N; i++) {
    // 如果未设置过
    if (dp[i] === undefined) {
      // 找到从[1,i-1]的所有约数
      let currentResult = false;
      for (let j = 1; j < i; j++) {
        if (i % j === 0) {
          if (dp[i - j] === false) {
            currentResult = true;
            break;
          }
        }
      }
      dp[i] = currentResult;
    }
  }
  return dp[N];
};

Matrix Block Sum

题目来源

https://leetcode.com/problems/matrix-block-sum/

难度：medium

题目描述

给定一个 m*n 的矩阵 mat 和一个正整数 K，返回一个 answer 数组，answer[i][j] 是所有 mat[r][c] 之和，r∈[i-K,i+K]，c∈[j-K,j+K]，并且 r/c 在数组 mat 中都是有效的位置

代码和说明

题目求的是矩形区域的面积，可以采用暴力O(n^4) 的方法求解，代码如下：遍历 mat 二维数组，对每个 i/j 计算所有满足条件的 r/c 之和，思路比较简单。

var matrixBlockSum = function (mat, K) {
  // fill([]) 的问题，对象引用同一个
  // const answer = new Array(mat.length).fill([]);
  const answer = new Array(mat.length).fill(0).map((item) => []);
  for (let i = 0; i < mat.length; i++) {
    for (let j = 0; j < mat[i].length; j++) {
      // 计算 dp[r][c] =  i - K <= r <= i + K, j - K <= c <= j + K
      let currentSum = 0;
      for (let r = i - K; r <= i + K; r++) {
        for (let c = j - K; c <= j + K; c++) {
          if (r >= 0 && r < mat.length && c >= 0 && c < mat[i].length) {
            currentSum += mat[r][c];
          }
        }
      }
      answer[i][j] = currentSum;
    }
  }
  return answer;
};

暴力法重复计算的次数较多，时间复杂度比较高，下面采用了动态规划法对其进行了优化：

矩形之和的求解利用了左边、上面和左上边三个大矩阵的结果，最后实际求解矩阵时，利用 dp 的结果可以很方便的求解出答案

// dp[i][j]：以 (i,j) 为右下角的矩阵之和
// basecase 为第一行和第一列，即为 mat[i][j]
// 状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i][j]

var matrixBlockSum = function (mat, K) {
  const dp = new Array(mat.length).fill(0).map((item) => []);
  const answer = new Array(mat.length).fill(0).map((item) => []);
  for (let i = 0; i < mat.length; i++) {
    for (let j = 0; j < mat[i].length; j++) {
      dp[i][j] = mat[i][j];
      if (i - 1 >= 0 && j - 1 >= 0) {
        dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
      } else if (i - 1 >= 0) {
        dp[i][j] += dp[i - 1][j];
      } else if (j - 1 >= 0) {
        dp[i][j] += dp[i][j - 1];
      }
    }
  }
  /**
   * r、c、K：
   * rl = i-K
   * rr = i+K
   * cl = j-K
   * cr = j+K
   *
   * answer[r][c] = dp[rr][cr] - dp[rr][cl-1] - dp[rl-1][cr] + dp[rl-1][cl-1]
   */
  for (let i = 0; i < mat.length; i++) {
    for (let j = 0; j < mat[i].length; j++) {
      // 处理超出的范围
      let rl = i - K < 0 ? 0 : i - K,
        rr = i + K > mat.length - 1 ? mat.length - 1 : i + K,
        cl = j - K < 0 ? 0 : j - K,
        cr = j + K > mat[i].length - 1 ? mat[i].length - 1 : j + K;
      answer[i][j] = dp[rr][cr];
      if (cl - 1 >= 0 && rl - 1 >= 0) {
        answer[i][j] =
          answer[i][j] - dp[rr][cl - 1] - dp[rl - 1][cr] + dp[rl - 1][cl - 1];
      } else if (cl - 1 >= 0) {
        answer[i][j] -= dp[rr][cl - 1];
      } else if (rl - 1 >= 0) {
        answer[i][j] -= dp[rl - 1][cr];
      }
    }
  }
  return answer;
};

Count Square Submatrices with All Ones

题目来源

https://leetcode.com/problems/count-square-submatrices-with-all-ones/

难度：medium

题目描述

给定一个只包括 0 和 1 的二维数组，返回所有子正方形的个数，正方形不能含 0

> Input: matrix =
> [
>   [0,1,1,1],
>   [1,1,1,1],
>   [0,1,1,1]
> ]
> Output: 15
> Explanation: 
> There are 10 squares of side 1.
> There are 4 squares of side 2.
> There is  1 square of side 3.
> Total number of squares = 10 + 4 + 1 = 15.
>

> Input: matrix = 
> [
>   [1,0,1],
>   [1,1,0],
>   [1,1,0]
> ]
> Output: 7
> Explanation: 
> There are 6 squares of side 1.  
> There is 1 square of side 2. 
> Total number of squares = 6 + 1 = 7.
>

代码和说明

/**
 * dp[i][j]：以 i/j 为右下角的矩阵有多少个 1*1、2*2、3*3... 矩阵
 * 例如：
 * [
 *  [0,1,1,1]         [0,1,1,1]
 *  [1,1,1,1]   ->    [1,1,2,2]
 *  [0,1,1,1]         [0,1,2,3]
 * ]
 *
 * basecase：第一行和第一列
 * 状态转移方程：dp[i][j] =
              Math.min(...[dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]]) + 1;
 */

var countSquares = function (matrix) {
  let result = 0;
  const dp = new Array(matrix.length).fill(0).map((item) => []);
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      if (matrix[i][j] === 0) {
        dp[i][j] = 0;
      } else {
        if (i - 1 >= 0 && j - 1 >= 0) {
          // 左、右和左上角存在
          // 如有三者有任意一个等于 0，则 dp[i][j]=1，否则等于三者最小值 +1
          if (
            matrix[i - 1][j] === 0 ||
            matrix[i][j - 1] === 0 ||
            matrix[i - 1][j - 1] === 0
          ) {
            dp[i][j] = 1;
          } else {
            dp[i][j] =
              Math.min(...[dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]]) + 1;
          }
        } else {
          // 左、右或左上角不存在
          dp[i][j] = 1;
        }
      }
      result += dp[i][j];
    }
  }
  return result;
};

Minimum Falling Path Sum

题目来源

https://leetcode.com/problems/minimum-falling-path-sum/

难度：medium

题目描述

给定一个 n*n 的二维数组，找到一条从第一行走到最后一行的最短路径。有条件限制：例如当前在第 i行 j 列，走到 i+1 行时，只能去下标合法的 j-1、j 或 j+1 列

代码和说明

// dp[i][j]：所有以 dp[i][j] 为终点的线路的最小值
// basecase：第一行
// 状态转移方程：dp[i][j] = Math.min(...[dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1]]) + A[i][j]

var minFallingPathSum = function (A) {
  const dp = new Array(A.length).fill(0).map((item) => []);
  for (let i = 0; i < A.length; i++) {
    for (let j = 0; j < A[i].length; j++) {
      if (i === 0) {
        // 初始化basecase
        dp[i][j] = A[i][j];
      } else {
        dp[i][j] = dp[i - 1][j];
        if (j - 1 >= 0) {
          dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
        }
        if (j + 1 < A[i].length) {
          dp[i][j] = Math.min(dp[i][j], dp[i - 1][j + 1]);
        }
        dp[i][j] += A[i][j];
      }
    }
  }
  return Math.min(...dp[dp.length - 1]);
};

Palindromic Substrings

题目来源

https://leetcode.com/problems/palindromic-substrings/

难度：medium

题目描述

给定一个字符串，返回字符串中回文字串的个数
1
2
3
4
> Input: "abc"
> Output: 3
> Explanation: Three palindromic strings: "a", "b", "c".
>

> Input: "aaa"
> Output: 6
> Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
>

代码和说明

有个小问题需要注意，动态规划的 dp 是依赖 dp[i+1][j-1] 的值，所以在计算 dp 前，其依赖的值需要提前被计算，所以可以修改一下遍历方式，斜着遍历：

如：(0,0)、(1,1,)、(2,2)…、(0,1)、(1,2)、(2,3)…、(0,2)、(1,3)、(2,4)…

// dp[i][j]：以 i 开始 j 结尾的字符串是不是回文
// basecase：长度为 1：true; 长度为 2：都相同=>true，不相同=>false
// 状态转移方程：dp[i][j] = dp[i+1][j-1] && s[i]===s[j]

var countSubstrings = function (s) {
  let result = 0;
  const dp = new Array(s.length).fill(0).map((item) => []);
  // 斜着遍历
  for (let step = 0; step < s.length; step++) {
    for (let i = 0; i < s.length - step; i++) {
      let j = step + i;
      // 处理长度为1
      if (i === j) {
        dp[i][j] = true;
        result++;
      } else if (i + 1 === j) {
        // 处理长度为2
        if (s[i] === s[j]) {
          dp[i][j] = true;
          result++;
        }
      } else {
        // 长度>=3
        if (dp[i + 1][j - 1] && s[i] === s[j]) {
          dp[i][j] = true;
          result++;
        }
      }
    }
  }
  return result;
};

Contents

Divisor Game

题目来源

题目描述

代码和说明

Matrix Block Sum

题目来源

题目描述

代码和说明

Count Square Submatrices with All Ones

题目来源

题目描述

代码和说明

Minimum Falling Path Sum

题目来源

题目描述

代码和说明

Palindromic Substrings

题目来源

题目描述

代码和说明