C++ | Leetcode C++题解之第312题戳气球

题目：

题解：

1. class Solution {
2. public:
3.     int maxCoins(vector<int>& nums) {
4.         int n = nums.size();
5.         vector<vector<int>> rec(n + 2, vector<int>(n + 2));
6.         vector<int> val(n + 2);
7.         val[0] = val[n + 1] = 1;
8.         for (int i = 1; i <= n; i++) {
9.             val[i] = nums[i - 1];
10.         }
11.         for (int i = n - 1; i >= 0; i--) {
12.             for (int j = i + 2; j <= n + 1; j++) {
13.                 for (int k = i + 1; k < j; k++) {
14.                     int sum = val[i] * val[k] * val[j];
15.                     sum += rec[i][k] + rec[k][j];
16.                     rec[i][j] = max(rec[i][j], sum);
17.                 }
18.             }
19.         }
20.         return rec[0][n + 1];
21.     }
22. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。