• Time:O(n^3)
• Space:O(n^2)

C++

``````class Solution {
public:
int getMoneyAmount(int n) {
// dp[i][j] := min money you need to guarantee a win of picking i..j
dp.resize(n + 1, vector<int>(n + 1, INT_MAX));
return getMoneyAmount(1, n);
}

private:
vector<vector<int>> dp;

int getMoneyAmount(int i, int j) {
if (i >= j)
return 0;
if (dp[i][j] != INT_MAX)
return dp[i][j];

for (int k = i; k <= j; ++k)
dp[i][j] =
min(dp[i][j],
max(getMoneyAmount(i, k - 1), getMoneyAmount(k + 1, j)) + k);

return dp[i][j];
}
};
``````

JAVA

``````class Solution {
public int getMoneyAmount(int n) {
// dp[i][j] := min money you need to guarantee a win of picking i..j
dp = new int[n + 1][n + 1];
Arrays.stream(dp).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
return getMoneyAmount(1, n);
}

private int[][] dp;

private int getMoneyAmount(int i, int j) {
if (i >= j)
return 0;
if (dp[i][j] != Integer.MAX_VALUE)
return dp[i][j];

for (int k = i; k <= j; ++k)
dp[i][j] = Math.min(
dp[i][j],
Math.max(getMoneyAmount(i, k - 1), getMoneyAmount(k + 1, j)) + k);

return dp[i][j];
}
}
``````

Python

``````class Solution:
def getMoneyAmount(self, n: int) -> int:
# dp(i, j) := min money you need to guarantee a win of picking i..j
@lru_cache(None)
def dp(i: int, j: int) -> int:
if i >= j:
return 0

ans = math.inf

for k in range(i, j + 1):
ans = min(ans, max(dp(i, k - 1), dp(k + 1, j)) + k)

return ans

return dp(1, n)
``````

• Time:O(n^3)
• Space:O(n^2)

C++

``````class Solution {
public:
int getMoneyAmount(int n) {
// dp[i][j] := min money you need to guarantee a win of picking i..j
vector<vector<int>> dp(n + 2, vector<int>(n + 2));

for (int d = 1; d < n; ++d)
for (int i = 1; i + d <= n; ++i) {
const int j = i + d;
dp[i][j] = INT_MAX;
for (int k = i; k <= j; ++k)
dp[i][j] = min(dp[i][j], max(dp[i][k - 1], dp[k + 1][j]) + k);
}

return dp[1][n];
}
};
``````

JAVA

``````class Solution {
public int getMoneyAmount(int n) {
// dp[i][j] := min money you need to guarantee a win of picking i..j
int[][] dp = new int[n + 2][n + 2];

for (int d = 1; d < n; ++d)
for (int i = 1; i + d <= n; ++i) {
final int j = i + d;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k <= j; ++k)
dp[i][j] = Math.min(dp[i][j], Math.max(dp[i][k - 1], dp[k + 1][j]) + k);
}

return dp[1][n];
}
}
``````

Python

``````class Solution:
def getMoneyAmount(self, n: int) -> int:
# dp[i][j] := min money you need to guarantee a win of picking i..j
dp = [[0] * (n + 2) for _ in range(n + 2)]

for d in range(1, n + 1):
for i in range(1, n - d + 1):
j = i + d
dp[i][j] = math.inf
for k in range(i, j + 1):
dp[i][j] = min(dp[i][j], max(dp[i][k - 1], dp[k + 1][j]) + k)

return dp[1][n]
``````