375.猜数字大小II

链接：375.猜数字大小II
难度：Medium
标签：数学、动态规划、博弈
简介：给你一个特定的数字 n ，返回能够 确保你获胜 的最小现金数，不管我选择那个数字 。

题解 1 - typescript

• 编辑时间：2021-11-12
• 执行用时：140ms
• 内存消耗：41.3MB
• 编程语言：typescript
• 解法介绍：动态规划。

function getMoneyAmount(n: number): number {
  const dp: number[][] = new Array(n + 1).fill(0).map(_ => new Array(n + 1).fill(0));
  for (let i = n; i >= 1; i--) {
    for (let j = i + 1; j <= n; j++) {
      let min = Infinity;
      for (let k = i; k < j; k++) {
        min = Math.min(min, k + Math.max(dp[i][k - 1], dp[k + 1][j]));
      }
      dp[i][j] = min;
    }
  }
  return dp[1][n];
}