forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0312-burst-balloons.c
30 lines (26 loc) · 889 Bytes
/
0312-burst-balloons.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int max(int a, int b) {
return (a > b) ? a : b;
}
int maxCoins(int* nums, int numsSize) {
// Add padding of 1 to both ends of the array
int n = numsSize + 2;
int paddedNums[n];
paddedNums[0] = paddedNums[n - 1] = 1;
for (int i = 1; i < n - 1; i++) {
paddedNums[i] = nums[i - 1];
}
// Create a 2D DP array to store the results
int dp[n][n];
memset(dp, 0, sizeof(dp));
// Start dynamic programming process
for (int len = 2; len < n; len++) {
for (int left = 0; left < n - len; left++) {
int right = left + len;
for (int k = left + 1; k < right; k++) {
dp[left][right] = max(dp[left][right],
paddedNums[left] * paddedNums[k] * paddedNums[right] + dp[left][k] + dp[k][right]);
}
}
}
return dp[0][n - 1];
}