- 375.猜数字大小II
- 题目描述
- 思路：动态规划
- Java实现
- Python实现
375.猜数字大小II 题目描述
猜数字大小II
思路：动态规划
为了将支付的金额最小化，除了需要将每次支付的金额控制在较低值外，还需要在猜数字的过程中缩小所选数字的范围。当猜了数字x且猜错的情况下，会知道x比所选数字大还是小。如果x比所选数字大，应该在比x小的数字中挑选数字猜。如果x比所选数字小，则应该在比x大的数字中挑选数字猜。
用f(i, j)表示在范围[i, j]内确保胜利的最少金额，目标是计算f(1, n)。
假定第一次猜的数字是x并且猜错，则需要支付金额x，当x大于所选数字时，为了确保胜利还需要支付的金额是f(1, x-1)，当x小于所选数字时，为了确保胜利还需要支付的金额是f(x+1, n)。为了在任何情况下都能确保胜利，应考虑最坏情况，计算f(1, n)时应取上述两者的最大值：f(1, n) = x + max(f(1, x-1), f(x+1, n))。
为了将确保胜利的金额最小化，需要遍历从1到n的所有可能的x，使得f(1, n)的值最小：
f
(
1
,
n
)
=
m
i
n
1
<
=
x
<
=
n
(
x
+
m
a
x
(
f
(
1
,
x
−
1
)
,
f
(
x
+
1
,
n
)
)
)
f(1, n) = min_{1<=x<=n}(x+max(f(1, x-1), f(x+1, n)))
f(1,n)=min1<=x<=n(x+max(f(1,x−1),f(x+1,n)))
由于f(1, x-1)和f(x+1, n)都是比原始问题f(1, n)规模更小的问题，因此可以使用动态规划进行求解。
动态规划的状态为f(i, j)，表示在范围[i, j]内确保胜利的最少金额。
当i = j时范围[i, j]只包含1个数字，则所选数字一定是范围内唯一的数字，不存在猜错的情况，因此，f(i, j)=0；当i > j 时，范围[i, j]不存在，f(i, j) = 0。
当i < j时，在范围[i, j]内第一次猜的数字可能是该范围内的任何一个数字。在第一次猜的数字是k的情况下(i <= k <= j)，在范围[i, j]内确保胜利的最少金额是k + max(f(i, k-1), f(k+1, j))。需要遍历全部可能的k找到在范围[i, j]内确保胜利的最少金额，因此状态转移方程如下：
f
(
i
,
j
)
=
m
i
n
i
<
=
k
<
=
j
(
k
+
m
a
x
(
f
(
i
,
k
−
1
)
,
f
(
k
+
1
,
j
)
)
)
f(i, j) = min_{i <= k <= j}(k+max(f(i, k-1), f(k+1, j)))
f(i,j)=mini<=k<=j(k+max(f(i,k−1),f(k+1,j)))
由于状态转移方程为根据规模小的子问题计算规模大的子问题，因此计算子问题的顺序为先计算规模小的子问题，后计算规模大的子问题，需要注意循环遍历的方向。
class Solution {
public int getMoneyAmount(int n) {
int[][] f = new int[n+1][n+1];
for (int i = n-1; i >= 1; i--) {
for (int j = i + 1; j <= n; j++) {
int minCost = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int cost = k + Math.max(f[i][k-1], f[k+1][j]);
minCost = Math.min(minCost, cost);
}
f[i][j] = minCost;
}
}
return f[1][n];
}
}
Python实现
class Solution:
def getMoneyAmount(self, n: int) -> int:
f = [[0] * (n+1) for i in range(n+1)]
for i in range(n-1, 0, -1):
for j in range(i+1, n+1):
f[i][j] = min(k+max(f[i][k-1], f[k+1][j]) for k in range(i, j))
return f[1][n]
