aboutsummaryrefslogtreecommitdiff
path: root/min_cost_cut_stick.cpp
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /min_cost_cut_stick.cpp
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'min_cost_cut_stick.cpp')
-rw-r--r--min_cost_cut_stick.cpp45
1 files changed, 45 insertions, 0 deletions
diff --git a/min_cost_cut_stick.cpp b/min_cost_cut_stick.cpp
new file mode 100644
index 0000000..5622868
--- /dev/null
+++ b/min_cost_cut_stick.cpp
@@ -0,0 +1,45 @@
+// 1547. Minimum Cost to Cut a Stick
+#include "leetcode.h"
+
+/*
+ * given a wooden stick of length 'n' units. the stick is labelled from 0 to
+ * 'n'. for example, a stick of length 6 is labelled as follows (see image).
+ * given an integer array 'cuts' where 'cuts[i]' denotes a position you should
+ * perform a cut at. you should perform the cuts in order, you can change the
+ * order of the cuts as you wish. the cost of one cut is the length of the stick
+ * to be cut, the total cost is the sum of costs of all cuts. when you cut a
+ * stick, it will be split into two smaller sticks ie. the sum of their lengths
+ * is the length of the stick before the cut. refer to first example for better
+ * explanation (see image). return minimum cost of the cuts
+ */
+
+class Solution {
+ int dp[102][102] = {};
+ int dfs(vector<int> &cuts, int i, int j) {
+ if (j - i <= 1)
+ return 0;
+ if (!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);
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<int> c1 = {1, 3, 4, 5};
+ vector<int> c2 = {5, 6, 1, 4, 2};
+ printf("%d\n", obj.minCost(7, c1)); // expect: 16
+ printf("%d\n", obj.minCost(9, c2)); // expect: 22
+}