312.戳气球_csdnc语言戳气球

思路

困难嘛？这是一个极其简单的dp问题。
我直接好家伙。

dp问题找两个关键

1. 状态表示
2. 状态计算

这里状态表示为f[i][j]， 状态表示可细分为：

1. 集合 ： 表示将区间[i + 1, j - 1]打完的所有方案
2. 属性 ： 最大值

这里i, j两个端点类似于哨兵，要用他俩来计算区间里打掉最后一个气球时的值。

状态计算：
枚举[i + 1, j - 1]中的每一个数，作为打掉的气球，假设其中的某一个数k是最后打掉的气球，那么又可以将区间划分成(i,k) 和 (k,j)，
所以最后的状态表示为,：
f[i][j] = f[i][k] + f[k] , [j] + nums[k] * nums[i] * nums[j];

取最大值max 即可

为了方便一开始可以建立一个新数组，头尾加上为1 的两个哨兵
因为状态计算的时候，每一个状态都依赖于比它本身更小的状态区间，那么我们就要枚举区间长度，从最小区间长度3一直到加了哨兵的nums.size() + 2的长度，为什么是3,因为在区间长度为3的时候f[i][j]可以由 0 + 0 + nums[k] * nums[k - 1] * nums[k + 1] 计算出来(长度为f[i][i + 1]时值为初始化的0)。

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

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19