// 区间 dp, 自下而上从左到右
// 时间O(n^3), 空间O(n^2)
const maxCoins = (nums: number[]): number => {
const n: number = nums.length;
const arr: Array<number> = new Array(n+2);
arr[0] = arr[n + 1] = 1;
for (let i: number = 1; i < n + 1; ++i) {
arr[i] = nums[i - 1];
}
// dp[i][j]: (i, j) 索引区间内能获得硬币的最大数量
const dp: Array<Array<number>> = new Array(n+2).fill(0).map(() => new Array(n+2).fill(0));
for (let i: number = n; i >= 0; --i) {
for (let j: number = i+1; j < n+2; ++j) {
for (let k: number = i+1; k < j; ++k) {
// 选取(i,j)最后一个被戳爆的索引
dp[i][j] = Math.max(dp[i][j], dp[i][k]+dp[k][j]+arr[i]*arr[j]*arr[k]);
}
}
}
return dp[0][n+1];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21