diff options
author | Jack Sangdahl <[email protected]> | 2025-06-27 12:23:02 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-27 12:23:02 -0600 |
commit | a96b65cbfad7f62f3db6b2eab105e4e25c0414c5 (patch) | |
tree | e2a2b3f49f9fb741be81415266ac93e74cff42ec /other/min_cost_cut_stick.cpp | |
parent | 694ad5ed71edcb1deccab54b72d706b779918276 (diff) | |
download | leetcode-a96b65cbfad7f62f3db6b2eab105e4e25c0414c5.tar.gz leetcode-a96b65cbfad7f62f3db6b2eab105e4e25c0414c5.zip |
chore: remove old cpp and rust solutions
Diffstat (limited to 'other/min_cost_cut_stick.cpp')
-rw-r--r-- | other/min_cost_cut_stick.cpp | 45 |
1 files changed, 0 insertions, 45 deletions
diff --git a/other/min_cost_cut_stick.cpp b/other/min_cost_cut_stick.cpp deleted file mode 100644 index 5622868..0000000 --- a/other/min_cost_cut_stick.cpp +++ /dev/null @@ -1,45 +0,0 @@ -// 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 -} |