問題描述：

有 n 個(gè)氣球，編號(hào)為0 到 n-1蕴坪，每個(gè)氣球上都標(biāo)有一個(gè)數(shù)字，這些數(shù)字存在數(shù)組 nums 中敬锐。
現(xiàn)在要求你戳破所有的氣球辞嗡。每當(dāng)你戳破一個(gè)氣球 i 時(shí)，你可以獲得 nums[left] * nums[i] * nums[right] 個(gè)硬幣滞造。 這里的 left 和 right 代表和 i 相鄰的兩個(gè)氣球的序號(hào)续室。注意當(dāng)你戳破了氣球 i 后，氣球 left 和氣球 right 就變成了相鄰的氣球谒养。
求所能獲得硬幣的最大數(shù)量挺狰。
示例：
輸入: [3,1,5,8]
輸出: 167
解釋: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 167

若氣球編號(hào)為0 到 n-1，當(dāng)最后戳破氣球k時(shí)买窟，此時(shí)數(shù)組里僅剩第k個(gè)氣球丰泊，因此得到的硬幣數(shù)應(yīng)該為nums[-1]*nums[k]*nums[n]。設(shè)從i到j(luò)編號(hào)的氣球得到的最大硬幣數(shù)為dp[i][j].
那么得到的總硬幣數(shù)應(yīng)該是dp[i][k]+dp[k][j]+nums[-1]*nums[k]*nums[n]始绍。若要找到最大的硬幣數(shù)瞳购，則需要找到最大的分割點(diǎn)k。
即可得到轉(zhuǎn)移方程：
dp[i][j] = max(dp[i][k]+dp[k][j]+nums[-1]*nums[k]*nums[n])
由于計(jì)算dp[i][j]需要(i,j)左側(cè)和下方的結(jié)果亏推，因此需要斜向遍歷学赛。
具體實(shí)現(xiàn)如下：

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        int n = nums.size();
        vector<int> t(n, 0);
        vector<vector<int>> dp(n, t);
        //dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])
        for(int len=2;len<n;len++)
        {
            for(int i=0;i+len<n;i++)
            {
                int j = i + len;
                for(int k=i+1;k<j;k++)
                {
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]);
                }
            }
        }
        return dp[0][n-1];
    }
};

與此類似的矩陣乘法問題。

問題描述：

給定n個(gè)矩陣：A1,A2,...,An吞杭，其中Ai與Ai+1是可乘的盏浇，i=1，2...芽狗，n-1绢掰。確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少童擎。輸入數(shù)據(jù)為矩陣個(gè)數(shù)和每個(gè)矩陣規(guī)模滴劲，輸出結(jié)果為計(jì)算矩陣連乘積的計(jì)算次序和最少數(shù)乘次數(shù)。

同樣需要找到合適的分割點(diǎn)k顾复，來得到最小值班挖。
其轉(zhuǎn)移方程為：
dp[i][j] = min(dp[i][k]+dp[k][j]+p[i-1]p[k]p[j]
其中，p[i-1]是第i個(gè)矩陣的行數(shù)捕透，p[j]是第j個(gè)矩陣的列數(shù)聪姿。