java 解法, 执行用时: 35 ms, 内存消耗: 41.5 MB, 提交时间: 2024-06-09 10:29:46

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[][] rec = new int[n + 2][n + 2];
        int[] val = new int[n + 2];
        val[0] = val[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 2; j <= n + 1; j++) {
                for (int k = i + 1; k < j; k++) {
                    int sum = val[i] * val[k] * val[j];
                    sum += rec[i][k] + rec[k][j];
                    rec[i][j] = Math.max(rec[i][j], sum);
                }
            }
        }
        return rec[0][n + 1];
    }
}

java 解法, 执行用时: 110 ms, 内存消耗: 41.6 MB, 提交时间: 2024-06-09 10:29:21

class Solution {
    public int[][] rec;
    public int[] val;

    public int maxCoins(int[] nums) {
        int n = nums.length;
        val = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        val[0] = val[n + 1] = 1;
        rec = new int[n + 2][n + 2];
        for (int i = 0; i <= n + 1; i++) {
            Arrays.fill(rec[i], -1);
        }
        return solve(0, n + 1);
    }

    public int solve(int left, int right) {
        if (left >= right - 1) {
            return 0;
        }
        if (rec[left][right] != -1) {
            return rec[left][right];
        }
        for (int i = left + 1; i < right; i++) {
            int sum = val[left] * val[i] * val[right];
            sum += solve(left, i) + solve(i, right);
            rec[left][right] = Math.max(rec[left][right], sum);
        }
        return rec[left][right];
    }
}

golang 解法, 执行用时: 36 ms, 内存消耗: 5.4 MB, 提交时间: 2023-05-24 17:36:11

func maxCoins(nums []int) int {
    n := len(nums)
    rec := make([][]int, n + 2)  // rec[i][j] 开区间(i, j)能拿到的最多硬币
    for i := 0; i < n + 2; i++ {
        rec[i] = make([]int, n + 2)
    }
    val := make([]int, n + 2)
    val[0], val[n+1] = 1, 1
    for i := 1; i <= n; i++ {
        val[i] = nums[i-1]
    }
    for i := n - 1; i >= 0; i-- {
        for j := i + 2; j <= n + 1; j++ {
            for k := i + 1; k < j; k++ {
                sum := val[i] * val[k] * val[j]
                sum += rec[i][k] + rec[k][j]
                rec[i][j] = max(rec[i][j], sum)
            }
        }
    }
    return rec[0][n+1]
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

golang 解法, 执行用时: 152 ms, 内存消耗: 5.5 MB, 提交时间: 2023-05-24 17:35:19

func maxCoins(nums []int) int {
    n := len(nums)
    val := make([]int, n + 2)
    for i := 1; i <= n; i++ {
        val[i] = nums[i - 1]
    }
    val[0], val[n+1] = 1, 1
    rec := make([][]int, n + 2)
    for i := 0; i < len(rec); i++ {
        rec[i] = make([]int, n + 2)
        for j := 0; j < len(rec[i]); j++ {
            rec[i][j] = -1
        }
    }
    return solve(0, n + 1, val, rec)
}

func solve(left, right int, val []int, rec [][]int) int {
    if left >= right - 1 {
        return 0
    }
    if rec[left][right] != -1 {
        return rec[left][right]
    }
    for i := left + 1; i < right; i++ {
        sum := val[left] * val[i] * val[right]
        sum += solve(left, i, val, rec) + solve(i, right, val, rec)
        rec[left][right] = max(rec[left][right], sum)
    }
    return rec[left][right]
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

python3 解法, 执行用时: 5568 ms, 内存消耗: 40 MB, 提交时间: 2023-05-24 17:34:46

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        val = [1] + nums + [1]
        
        @lru_cache(None)
        def solve(left: int, right: int) -> int:
            if left >= right - 1:
                return 0
            
            best = 0
            for i in range(left + 1, right):
                total = val[left] * val[i] * val[right]
                total += solve(left, i) + solve(i, right)
                best = max(best, total)
            
            return best

        return solve(0, n + 1)

python3 解法, 执行用时: 2756 ms, 内存消耗: 18.1 MB, 提交时间: 2023-05-24 17:34:15

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        #nums首尾添加1，方便处理边界情况
        nums.insert(0,1)
        nums.insert(len(nums),1)

        store = [[0]*(len(nums)) for i in range(len(nums))]

        def range_best(i,j):
            m = 0 
            #k是(i,j)区间内最后一个被戳的气球
            for k in range(i+1,j): #k取值在(i,j)开区间中
                #以下都是开区间(i,k), (k,j)
                left = store[i][k]
                right = store[k][j]
                a = left + nums[i]*nums[k]*nums[j] + right
                if a > m:
                    m = a
            store[i][j] = m

        #对每一个区间长度进行循环
        for n in range(2,len(nums)): #区间长度 #长度从3开始，n从2开始
            #开区间长度会从3一直到len(nums)
            #因为这里取的是range，所以最后一个数字是len(nums)-1

            #对于每一个区间长度，循环区间开头的i
            for i in range(0,len(nums)-n): #i+n = len(nums)-1

                #计算这个区间的最多金币
                range_best(i,i+n)

        return store[0][len(nums)-1]

python3 解法, 执行用时: 6524 ms, 内存消耗: 40 MB, 提交时间: 2023-05-24 17:33:07

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

        @cache
        def solve(L, R):
            # 要戳nums[L:R+1]
            if L > R:
                return 0

            # 把 L 留最后戳
            ret = nums[L-1]*nums[L]*nums[R+1] + solve(L+1, R)
            # 把 R 留最后戳
            ret = max(ret, nums[L-1]*nums[R]*nums[R+1] + solve(L, R-1))
            # 把k留最后戳
            for k in range(L+1, R):
                # 先戳 nums[L:k] 和 nums[k+1:R+1], 再戳 nums[k]
                cur = solve(L, k-1) + nums[L-1]*nums[k]*nums[R+1] + solve(k+1, R)
                ret = max(ret, cur)

            return ret
            
        return solve(1, n)

javascript 解法, 执行用时: 196 ms, 内存消耗: 43.9 MB, 提交时间: 2023-05-24 17:32:36

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function (nums) {
  let n = nums.length;
  // 添加两侧的虚拟气球
  let points = new Array(n + 2);
  points[0] = points[n + 1] = 1;
  for (let i = 1; i <= n; i++) {
    points[i] = nums[i - 1];
  }
  // base case 已经都被初始化为 0
  let dp = new Array(n + 2).fill(0).map(() => new Array(n + 2).fill(0));
  // 开始状态转移
  // i 应该从下往上
  for (let i = n; i >= 0; i--) {
    // j 应该从左往右
    for (let j = i + 1; j < n + 2; j++) {
      // 最后戳破的气球是哪个？
      for (let k = i + 1; k < j; k++) {
        // 择优做选择
        dp[i][j] = Math.max(
          dp[i][j],
          dp[i][k] + dp[k][j] + points[i] * points[j] * points[k]
        );
      }
    }
  }
  return dp[0][n + 1];
};

cpp 解法, 执行用时: 436 ms, 内存消耗: 10.2 MB, 提交时间: 2023-05-24 17:31:58

/**
当求戳爆开区间（i,j）内部所有气球可获的最大硬币数时，可以分为三步：

step 1: 选取一个最后戳爆的气球 k (需要选取每个可能的k去计算一遍，保留最大结果)

step 2: 戳爆开区间（i, k）内的气球，再戳爆开区间（k, j）内的气球，完成后开区间内只剩下气球 k, 其左右气球为 i , j

step 3: 戳爆气球 k, 获得硬币数为 nums[i]∗nums[k]∗nums[j]

当我们在开头和结尾加上边界值1时，数组长度为 len = nums.size() + 2，则我们的目标就是开区间（0， len-1）
 */
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        // dp(i, j): 开区间(i, j)所能取得的最大硬币数量
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        int len = nums.size();
        vector<vector<int>> dp(len, vector<int>(len, 0));
        for(int i = len-1; i >=0; --i){ // i逆序：dp[k][j]中的k大于i
            for(int j = i+2; j <= len-1; ++j){ // j-i <= 1时区间为空，所以j从i+2开始
                for(int k = i+1; k < j; ++k){ // k取不到边界值，因为是空区间
                    dp[i][j] = max(dp[i][j], dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]);
                }
                
            }
        }
        return dp[0][len-1];
    }
};