leetcode

commit 30d838aed5651a917c0180269fddcf3971aa195f
parent 99a39c006ef65108fb12ff7e989350acf4a91e69
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 14 Jan 2024 16:50:02 +0000

1 Random Problem

Diffstat:
A
Problems/1039.cpp
 | 
26
++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 27 insertions(+), 0 deletions(-)
diff --git a/Problems/1039.cpp b/Problems/1039.cpp
@@ -0,0 +1,26 @@
+class Solution {
+    static int dp[51][51];
+
+    static int solve(const int *data, int low, int high) {
+        if (high - low < 2) return 0;
+        if (dp[low][high] != -1) return dp[low][high];
+        int res = INT_MAX;
+        if (high - low == 2)
+            res = data[low] * data[low + 1] * data[low + 2];
+        else {
+            const int base = data[low] * data[high];
+            for (int i = low + 1; i < high; i++) {
+                res = min(res, base * data[i] + solve(data, low, i) + solve(data, i, high));
+            }
+        }
+        return dp[low][high] = res;
+    }
+
+  public:
+    Solution() { memset(dp, 0xFF, sizeof(dp)); }
+    int minScoreTriangulation(const vector<int> &values) const {
+        return solve(values.data(), 0, size(values) - 1);
+    }
+};
+
+int Solution::dp[51][51];
diff --git a/README.md b/README.md
@@ -564,6 +564,7 @@ for solving problems.
 |  1031  |   Medium   | [Maximum Sum of Two Non-Overlapping Subarrays](Problems/1031.cpp)                                  |
 |  1035  |   Medium   | [Uncrossed Lines](Problems/1035.cpp)                                                               |
 |  1038  |   Medium   | [Binary Search Tree to Greater Sum Tree](Problems/1038.cpp)                                        |
+|  1039  |   Medium   | [Minimum Score Triangulation of Polygon](Problems/1039.cpp)                                        |
 |  1042  |   Medium   | [Flower Planting With No Adjacent](Problems/1042.cpp)                                              |
 |  1043  |   Medium   | [Partition Array for Maximum Sum](Problems/1043.cpp)                                               |
 |  1045  |   Medium   | [Customers Who Bought All Products](Problems/1045.cpp)                                             |