LeetCode：375. 猜数字大小 II

如何理解“确保获胜的最小现金”？

1. 最坏情况：当猜数字 $k$ 时，如果猜错了，那么目标数字可能在左边，也可能在右边。为了确保能赢，需要准备应对更费钱的那一边
2. 最优策略：虽然需要应对最坏情况，但是可以通过选择「第一次、第二次…猜哪个数字」，使得该「最坏情况下的开销」尽可能小

状态定义#

设 $dp[i][j]$ 为：从 $i$ 到 $j$ 这个范围内，确保能赢所需要准备的最少钱数。

• 目标：求 $dp[1][n]$
• 初始化：当 $i \ge j$ 时，$dp[i][j] = 0$，因为只有一个数字（一下子就能猜对）或者没有数字了，不用付钱。

状态转移方程#

假设在区间 $[i, j]$ 猜数字 $k$（其中 $i \le k \le j$）

1. 如果猜 $k$ 猜错了，需要支付 $k$ 元
2. 接下来，目标数字要么在左区间 $[i, k - 1]$，要么在右区间 $[k + 1, j]$
3. 为了确保能赢，至少需要准备 $k + max(dp[i][k - 1], dp[k + 1][j])$
4. 同时为求最优策略，我们需要枚举所有的 $k$，取其中的最小值

状态转移公式： $dp[i][j] = \min_{i \le k \le j} \{ k + \max(dp[i][k-1], dp[k+1][j]) \}$

代码实现#

public int getMoneyAmount(int n) {
	// dp[i][j] 表示从 i 到 j 确保获胜的最小金额
	// n + 2是为了防止 k + 1溢出
	int[][] dp = new int[n + 2][n + 2];

	// 枚举区间长度 len，从长度 2 开始（长度 1 的开销是 0）
	for (int len = 2; len <= n; len++) {
		// 枚举左端点 i
		for (int i = 1; i <= n - len + 1; i++) {
			int j = i + len - 1; // 右端点
			
			dp[i][j] = Integer.MAX_VALUE;

			// 枚举在该区间内第一次猜哪个数字 k
			for (int k = i; k <= j; k++) {
				int res = k + Math.max(dp[i][k - 1], dp[k + 1][j]);
				dp[i][j] = Math.min(dp[i][j], res);
			}
		}
	}
	return dp[1][n];
}