algo/di-er-zhan-a01c6/yong-dong--63ceb/jing-dian--3c814/

[giscus[bot]]

algo/di-er-zhan-a01c6/yong-dong--63ceb/jing-dian--3c814/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！ 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 :----: :----: :----: 312. Burst...

https://labuladong.gitee.io/algo/di-er-zhan-a01c6/yong-dong--63ceb/jing-dian--3c814/

[Youarenotblind]

#define MAX(A, B) ((A) > (B) ? (A) : (B))

int dp(int * newNums, int newNumsSize, int i, int j, int ** memo)
{
    if(j <= i + 1)
        return 0;
    if(memo[i][j] != -1)
        return memo[i][j];
    
    int res = 0;
    for(int k = i + 1; k < j; k++)
        res = MAX(res, dp(newNums, newNumsSize, i, k, memo) + dp(newNums, newNumsSize, k, j, memo) + newNums[i] * newNums[j] * newNums[k]);

    memo[i][j] = res;
    return memo[i][j];
}

int maxCoins(int* nums, int numsSize)
{
    int ** memo = (int **)malloc(sizeof(int *) * (numsSize + 2));
    for(int i = 0; i < numsSize + 2; i++)
    {
        memo[i] = (int *)malloc(sizeof(int) * (numsSize + 2));
        for(int j = 0; j < numsSize + 2; j++)
            memo[i][j] = -1;
    }

    int * newNums = malloc(sizeof(int) * (numsSize + 2));
    newNums[0] = 1;
    for(int i = 1; i <= numsSize; i++)
        newNums[i] = nums[i-1];
    newNums[numsSize+1] = 1;

    int ans = dp(newNums, numsSize + 2, 0, numsSize + 1, memo);

    for(int i = 0; i < numsSize + 2; i++)
        free(memo[i]);
    free(memo);
    free(newNums);
    return ans;
}