commit 3249a078cdc8e32636cb365184825213b9bc13de
parent 12af5344843e003e9aaf70ee327e8295ed670055
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sun, 28 May 2023 17:45:33 +0200
Daily Problem
Diffstat:
2 files changed, 23 insertions(+), 1 deletion(-)
diff --git a/Problems/1547.cpp b/Problems/1547.cpp
@@ -0,0 +1,21 @@
+class Solution {
+ int dp[102][102] = {};
+
+ int dfs(const vector<int> &cuts, int i, int j) {
+ if (j - i <= 1) return 0;
+ if (dp[i][j]) return dp[i][j];
+ dp[i][j] = INT_MAX;
+ for (auto k = i + 1; k < j; ++k)
+ dp[i][j] =
+ min(dp[i][j], cuts[j] - cuts[i] + dfs(cuts, i, k) + dfs(cuts, k, j));
+ return dp[i][j];
+ }
+
+public:
+ int minCost(int n, vector<int> &cuts) {
+ cuts.push_back(0);
+ cuts.push_back(n);
+ sort(begin(cuts), end(cuts));
+ return dfs(cuts, 0, cuts.size() - 1);
+ }
+};
diff --git a/README.md b/README.md
@@ -413,7 +413,7 @@ for solving problems.
| 1099 | Easy | [Replace Elements with Greatest Element on Right Side](Problems/1099.cpp) |
| 1129 | Medium | [Shortest Path with Alternating Colors](Problems/1129.cpp) |
| 1137 | Easy | [N-th Tribonacci Number](Problems/1137.cpp) |
-| 1140 | Medium | [Stone Game II](Problems/1140.cpp) |
+| 1140 | Medium | [Stone Game II](Problems/1140.cpp) |
| 1143 | Medium | [Longest Common Subsequence](Problems/1143.cpp) |
| 1162 | Medium | [As Far from Land as Possible](Problems/1162.cpp) |
| 1202 | Medium | [Smallest String With Swaps](Problems/1202.cpp) |
@@ -464,6 +464,7 @@ for solving problems.
| 1523 | Easy | [Count Odd Numbers in an Interval Range](Problems/1523.cpp) |
| 1539 | Easy | [Kth Missing Positive Number](Problems/1539.cpp) |
| 1544 | Easy | [Make The String Great](Problems/1544.cpp) |
+| 1547 | Hard | [Minimum Cost to Cut a Stick](Problems/1547.cpp) |
| 1557 | Medium | [Minimum Number of Vertices to Reach All Nodes](Problems/1557.cpp) |
| 1567 | Medium | [Maximum Length of Subarray With Positive Product](Problems/1567.cpp) |
| 1572 | Easy | [Matrix Diagonal Sum](Problems/1572.cpp) |
