C 解法, 执行用时: 4ms, 内存消耗: 404KB, 提交时间: 2022-06-24

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param coins int整型一维数组 
 * @param coinsLen int coins数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

int max(int a, int b) {
    return a > b ? a : b;
}

int getCoins(int* coins, int coinsLen ) {
    int coinExt[coinsLen + 2];
    for (int i = 0; i < coinsLen + 2; i++) {
        if (i == 0 || (i == coinsLen +1)) {
            coinExt[i] = 1;
        } else {
            coinExt[i] = coins[i-1];
        }
    }
    int dp[coinsLen][coinsLen];
    for (int i = 0; i < coinsLen; i++) {
        memset(dp[i], 0, sizeof(dp[i]));
        dp[i][i] = coinExt[i]*coinExt[i+1]*coinExt[i+2];
    }
    
    for (int l = coinsLen - 1; l>=0; l--) {
        for (int r = l + 1; r < coinsLen; r++) {
            dp[l][r] = dp[l][r-1] + coinExt[l] * coinExt[r+1] * coinExt[r+2];
            
            dp[l][r] = max(dp[l][r], dp[l+1][r] + coinExt[l] * coinExt[l+1] * coinExt[r+2]);
            
            for (int i = l; i < r-1; i++) {
                dp[l][r] = max(dp[l][r], dp[l][i] + dp[i+2][r] + coinExt[l] * coinExt[i+2] * coinExt[r+2]);
            }
        }
    }
    
    return dp[0][coinsLen - 1];
}

C++ 解法, 执行用时: 4ms, 内存消耗: 420KB, 提交时间: 2022-07-19

class Solution {
  public:
    int getCoins(vector<int>& coins) {
        int h = coins.size();
        vector<vector<int>> v(h + 2, vector<int>(h+ 2, 0));
        vector<int> e(h + 2, 1);       
        for (int i = 1; i < h + 1; i ++) {
            e[i] = coins[i - 1];
        }
        
        for (int j = 2; j <= h + 1; j ++) {
            for (int i = j - 2; i >= 0; i --) {
                for (int k = i + 1; k < j; k ++) {
                    int L = e[i], R = e[j];
                    v[i][j] = max(v[i][j], L * R * e[k] + v[i][k] + v[k][j]);
                }
            }
        }
        return v[0][h + 1];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 424KB, 提交时间: 2022-07-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param coins int整型vector 
     * @return int整型
     */
    int getCoins(vector<int>& coins) {
        // write code here
        int n = coins.size();
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        vector<int> temp(n + 2, 1);
        for(int i = 1; i < n + 1; i ++){
            temp[i] = coins[i - 1];
        }
        for(int j = 2; j <= n + 1; j ++){
            for(int i = j - 2; i >= 0; i --){
                for(int k = i + 1; k < j; k ++){
                    int left = temp[i], right = temp[j];
                    dp[i][j] = max(dp[i][j], left * right * temp[k] + dp[i][k]+ dp[k][j]);
                }
            }
        }
        return dp[0][n + 1];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 428KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param coins int整型vector 
     * @return int整型
     */
    int getCoins(vector<int>& coins) {
        // write code here
        int h=coins.size();
        vector<vector<int>> v(h+2,vector<int>(h+2,0));
        vector<int> e(h+2,1);
        for(int i=1;i<h+1;i++)
        {
            e[i]=coins[i-1];
        }
        for(int j=2;j<=h+1;j++)
        {
            for(int i=j-2;i>=0;i--)
            {
                for(int k=i+1;k<j;k++)
                {
                    int L=e[i],R=e[j];
                    v[i][j]=max(v[i][j],L*R*e[k]+v[i][k]+v[k][j]);
                }
            }
        }
        return v[0][h+1];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 432KB, 提交时间: 2022-05-12

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param coins int整型vector 
     * @return int整型
     */

    int getCoins(vector<int>& coins) {
        // write code here
        int len=coins.size();
        if(len==0)    return 0;
        vector<int> helper(len+2,1);
        for(int i=1;i<=len;i++)
        {
            helper[i]=coins[i-1];
        }
        vector<vector<int>>  dp(len+2,vector<int>(len+2));
        for(int i=1;i<=len;i++)
        {
            dp[i][i]=helper[i]*helper[i-1]*helper[i+1];
        }
        for(int l=len;l>=1;l--)
        {
            for(int r=l+1;r<=len;r++)
            {
                int fl=dp[l+1][r]+helper[l]*helper[l-1]*helper[r+1];
                int fr=dp[l][r-1]+helper[r]*helper[l-1]*helper[r+1];
                dp[l][r]=max(fl,fr);
                for(int i=l+1;i<r;i++)
                    dp[l][r]=max(dp[l][r],dp[l][i-1]+dp[i+1][r]+helper[i]*helper[l-1]*helper[r+1]);
            }
        }
        return dp[1][len];
    }
};