leetcode

commit 5d6cfa885dab203135d66bf59515764164c2927b
parent eaca2c5a02e5c9c33ba3b5b7798d28604e2d85e1
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 25 Oct 2024 11:15:54 +0200

1 Random Problem

Diffstat:
A
Problems/0312.cpp
 | 
25
+++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 26 insertions(+), 0 deletions(-)
diff --git a/Problems/0312.cpp b/Problems/0312.cpp
@@ -0,0 +1,25 @@
+class Solution {
+  public:
+    int maxCoins(vector<int> &nums) const {
+        nums.insert(begin(nums), 1);
+        nums.push_back(1);
+
+        const int n = size(nums);
+        static int dp[303][303];
+
+        // dp[i][j]: coins obtained from bursting all the balloons between index i and j (not including i or
+        // j) dp[i][j] = max(nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]) (k in (i+1,j))
+
+        memset(dp, 0x00, sizeof(dp));
+        for (int d = 2; d < n; d++) {
+            for (int l = 0; l < n - d; l++) {
+                const int r = l + d;
+                for (int k = l + 1; k < r; k++) {
+                    dp[l][r] = max(dp[l][r], nums[l] * nums[k] * nums[r] + dp[l][k] + dp[k][r]);
+                }
+            }
+        }
+
+        return dp[0][n - 1];
+    }
+};
diff --git a/README.md b/README.md
@@ -287,6 +287,7 @@ for solving problems.
 |  0307  |   Medium   | [Range Sum Query - Mutable](Problems/0307.cpp)                                                     |
 |  0309  |   Medium   | [Best Time to Buy and Sell Stock with Cooldown](Problems/0309.cpp)                                 |
 |  0310  |   Medium   | [Minimum Height Trees](Problems/0310.cpp)                                                          |
+|  0312  |    Hard    | [Burst Balloons](Problems/0312.cpp)                                                                |
 |  0315  |    Hard    | [Count of Smaller Numbers After Self](Problems/0315.cpp)                                           |
 |  0316  |   Medium   | [Remove Duplicate Letters](Problems/0316.cpp)                                                      |
 |  0318  |   Medium   | [Maximum Product of Word Lengths](Problems/0318.cpp)                                               |