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

## C++

``````class Solution {
public:
int maxCoins(vector<int>& nums) {
const int n = nums.size();

nums.insert(begin(nums), 1);
nums.insert(end(nums), 1);

// dp[i][j] := maxCoins(nums[i..j])
dp.resize(n + 2, vector<int>(n + 2));
return maxCoins(nums, 1, n);
}

private:
vector<vector<int>> dp;

int maxCoins(vector<int>& nums, int i, int j) {
if (i > j)
return 0;
if (dp[i][j])
return dp[i][j];

for (int k = i; k <= j; ++k)
dp[i][j] = max(dp[i][j],
maxCoins(nums, i, k - 1) +
maxCoins(nums, k + 1, j) +
nums[i - 1] * nums[k] * nums[j + 1]);

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

## JAVA

``````class Solution {
public int maxCoins(int[] nums) {
final int n = nums.length;

A = new int[n + 2];

System.arraycopy(nums, 0, A, 1, n);
A[0] = 1;
A[n + 1] = 1;

// dp[i][j] := maxCoins(A[i..j])
dp = new int[n + 2][n + 2];
return maxCoins(1, n);
}

private int[][] dp;
private int[] A;

private int maxCoins(int i, int j) {
if (i > j)
return 0;
if (dp[i][j] > 0)
return dp[i][j];

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

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

## Python

``````class Solution:
def maxCoins(self, nums: List[int]) -> int:
A = [1] + nums + [1]

@lru_cache(None)
def dp(i: int, j: int) -> int:
if i > j:
return 0

return max(dp(i, k - 1) + dp(k + 1, j) + A[i - 1] * A[k] * A[j + 1]
for k in range(i, j + 1))

return dp(1, len(nums))
``````

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

## C++

``````class Solution {
public:
int maxCoins(vector<int>& nums) {
const int n = nums.size();

nums.insert(begin(nums), 1);
nums.insert(end(nums), 1);

// dp[i][j] := maxCoins(nums[i..j])
vector<vector<int>> dp(n + 2, vector<int>(n + 2));

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

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

## JAVA

``````class Solution {
public int maxCoins(int[] nums) {
final int n = nums.length;
int[] A = new int[n + 2];
System.arraycopy(nums, 0, A, 1, n);
A[0] = 1;
A[n + 1] = 1;

// dp[i][j] := maxCoins(A[i..j])
int[][] dp = new int[n + 2][n + 2];

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

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

## Python

``````class Solution:
def maxCoins(self, nums: List[int]) -> int:
n = len(nums)
A = [1] + nums + [1]
dp = [[0] * (n + 2) for _ in range(n + 2)]

for d in range(n):
for i in range(1, n - d + 1):
j = i + d
for k in range(i, j + 1):
dp[i][j] = max(
dp[i][j],
dp[i][k - 1] +
dp[k + 1][j] +
A[i - 1] * A[k] * A[j + 1])

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