BU
unknown
python
2 years ago
360 B
83
Indexable
Never
class Solution: def getMoneyAmount(self, n: int) -> int: dp = [[0] * (n+1) for _ in range(n+1)] for length in range(2, n+1): for start in range(1, n-length+2): end = start + length - 1 dp[start][end] = min(i + max(dp[start][i-1], dp[i+1][end]) for i in range(start, end)) return dp[1][n]