19 lines
571 B
Python
19 lines
571 B
Python
def min_cost_to_win(n):
|
|
dp = [[0] * (n + 2) for _ in range(n + 2)]
|
|
for length in range(2, n + 1):
|
|
for i in range(1, n - length + 2):
|
|
j = i + length - 1
|
|
best = 10**9
|
|
for p in range(i, j + 1):
|
|
left = dp[i][p - 1] if p > i else 0
|
|
right = dp[p + 1][j] if p < j else 0
|
|
best = min(best, p + max(left, right))
|
|
dp[i][j] = best
|
|
return dp[1][n]
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print(min_cost_to_win(1))
|
|
print(min_cost_to_win(2))
|
|
print(min_cost_to_win(10))
|