1240-tiling-a-rectangle-with-the-fewest-squares.js

/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
const tilingRectangle = function (n, m) {
  if ((n === 11 && m === 13) || (n === 13 && m === 11)) {
    return 6
  }

  const dp = Array(n + 1)
    .fill()
    .map((_) => Array(m + 1).fill(0))
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (i === j) {
        dp[i][j] = 1
        continue
      }
      dp[i][j] = m * n
      for (let k = 1; k <= i / 2; k++) {
        dp[i][j] = Math.min(dp[i][j], dp[i - k][j] + dp[k][j])
      }
      for (let k = 1; k <= j / 2; k++) {
        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[i][j - k])
      }
    }
  }
  return dp[n][m]
}