LeetCode Solutions
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];
}
};
|
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];
}
}
|
class Solution:
def maxCoins(self, nums: List[int]) -> int:
A = [1] + nums + [1]
@functools.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))
|
