分析
dp[i][j]表示[i,j]范围中需要全部猜到的最小花费 i <= j
我们要求 dp[1][n]
首先对于dp[i][i]显然是0
其次由于贪心对于dp[i][i + 1]显然是i
然后一般情况我们把i从后往前遍历(n, 0, -1)
j从(i + 2，n + 1）遍历
然后从(i, j)中选定mid就是猜的数字
这样就会划分成dp[i][mid - 1] 和 dp[mid + 1][j]两个区域
这里我们要做最坏的打算也就是取max
然后加上mid后，对于各个mid的结果要做最优的打算也就是取min
因此
cur = min(cur, mid + max(dp[i][mid - 1], dp[mid + 1][j]))
上面这个核心的递推式子就出来了~
ac code
class Solution:
def getMoneyAmount(self, n: int) -> int:
# dp[i][j]表示从【1，n】的最小花费
dp = [[0] * (n + 1) for _ in range(n + 1)]
# i = j and j = i + 1初始
for i in range(1, n):
dp[i][i] = 0
dp[i][i + 1] = i # 这里是贪心
# 倒着来
for i in range(n, 0, -1):
for j in range(i + 2, n + 1):
cur = inf
# 遍历可能猜的数mid
for mid in range(i, j):
# 最坏情况中的最好情况
# 选定了mid以后就要看最坏的情况
# 然后从各个mid中选到最好的情况
cur = min(cur, mid + max(dp[i][mid - 1], dp[mid + 1][j]))
dp[i][j] = cur
return dp[1][n]
总结
dp由点及面
可得到dp[i][i]和dp[i][i + 1]
然后通过遍历i,j
再从(i,j)遍历mid
mid分成的两个子区域考虑最坏也就是max
加上mid后考虑最好也就是min即可
非常经典的由点及面 + 大问题化小问题
非常经典！
