/**
 * @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]
}