/**
* @param {number[]} nums
* @return {number}
*/
const maxCoins = function (nums) {
let len = 0;
for (let i = 0, ii = nums.length; i < ii; ++i) {
if (nums[i] > 0) {
nums[len++] = nums[i];
}
}
nums.unshift(1);
nums[++len] = 1;
let dp = new Array();
for (let i = 0; i < len; i++) {
dp[i] = new Array();
for (let j = 0; j < len; j++) {
dp[i][j] = 0;
}
}
// console.log(divide(dp, nums, 0, len));
return divide(dp, nums, 0, len);
};
const divide = function (dp, nums, left, right) {
if (left + 1 === right) {
return 0;
}
if (dp[left][right] > 0) {
return dp[left][right];
}
let ans = 0;
for (let i = left + 1; i < right; ++i) {
ans = Math.max(ans, nums[left] * nums[i] * nums[right] + divide(dp, nums, left, i) + divide(dp, nums, i, right));
}
dp[left][right] = ans;
return ans
}
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
nums.insert(nums.begin(), 1);
nums.push_back(1);
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
for (int len = 1; len <= n; ++len) {
for (int i = 1; i <= n - len + 1; ++i) {
int j = i + len - 1;
for (int k = i; k <= j; ++k) {
dp[i][j] = max(dp[i][j], nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j]);
}
}
}
return dp[1][n];
}
};
自己实现的DP版本,发现变量名起对了,对理解代码很有效 ,unitlen在这里是每次更新的区间大小,查看console.log(i, j, i + unitlen - 1)就明白了
const maxCoins = function (nums) {
let len = 0;
for (let i = 0, ii = nums.length; i < ii; ++i) {
if (nums[i] > 0) {
nums[len++] = nums[i];
}
}
nums.unshift(1);
nums[++len] = 1;
let dp = new Array();
for (let i = 0; i < len + 1; i++) {
dp[i] = new Array();
for (let j = 0; j < len + 1; j++) {
dp[i][j] = 0;
}
}
// console.log(nums, len);
for (let unitlen = 1; unitlen < len; unitlen++) {
for (let i = 1; i < len - unitlen + 1; i++) {
for (let j = i; j < i + unitlen; j++) {
// console.log(i, j, i + unitlen - 1);
dp[i][i + unitlen - 1] = Math.max(dp[i][i + unitlen - 1], dp[i][j - 1] + dp[j + 1][i + unitlen - 1] + nums[i - 1] * nums[j] * nums[i + unitlen])
}
}
}
return dp[1][len-1]
}