We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.
However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
Example:
n = 10, I pick 8.
- First round: You guess 5, I tell you that it's higher. You pay $5.
- Second round: You guess 7, I tell you that it's higher. You pay $7.
- Third round: You guess 9, I tell you that it's lower. You pay $9.
Game over. 8 is the number I picked.
You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
Python Solution 1:
# 1918ms
class Solution(object):
def getMoneyAmount(self, n):
"""
:type n: int
:rtype: int
"""
dp = {(i, i): 0 for i in range(1, n + 1)}
for i in range(1, n):
for j in range(1, n - i + 1):
dp[j, j + i] = j + i + dp[j, j + i - 1]
for k in range(j, j + i):
dp[j, j + i] = min(dp[j, j + i], max(dp.get((j, k - 1), 0), dp.get((k + 1, j + i), 0)) + k)
return dp[1, n]
Python Solution 2:
# 2405ms
class Solution(object):
def getMoneyAmount(self, n):
"""
:type n: int
:rtype: int
"""
cache = {}
def recu(s, e):
if s >= e: return 0
if (s, e) in cache: return cache[(s, e)]
res = min(s + recu(s + 1, n), e + recu(s, e - 1))
for i in range(s + 1, e):
res = min(res, i + max(recu(s, i - 1), recu(i + 1, e)))
cache[(s, e)] = res
return res
return recu(1, n)
Python Solution 3:
# 608ms
class Solution(object):
def getMoneyAmount(self, n):
"""
:type n: int
:rtype: int
"""
dp = []
for _ in range(n + 1):
dp.append([0] * (n + 1))
for i in range(1, n):
for j in range(1, n - i + 1):
dp[j][j + i] = j + dp[j + 1][j + i]
for k in range(j + i // 2, j + i):
dp[j][j + i] = min(dp[j][j + i], max(dp[j][k - 1], dp[k + 1][j + i]) + k)
return dp[1][n]
Summary:
- dp is so funny.
LeetCode: 375. Guess Number Higher or Lower II
近期评论