🌱 Keegan's Digital Garden

1547. Minimum Cost to Cut a Stick

3 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- question description doesn't make any sense 
	- should perform the cuts in order
	- you can change the order of cuts as you wish?

- somewhat of a permutation problem
	- brute force approach would involve searching all possible orders to make the cuts
	- this would be O(c!) which is exponential in growth

- dynamic programming would lend well to this problem 
	- the cost to cut the stick into smaller segments often depends on overlapping computations

- why not greedy?
	- cutting at a "locally optimal" position (like the smallest cut) doesn't work well in this case since the minimum cost depends on the order of the cuts

🤔What Did I Struggle With?

- question phrasing didnt make sense 
- defining what determines the cost of a cut

💡 Explanation of Solution

1. Add boundaries to cuts
	- the problem implicitly assumes that the stick starts at `0` and ends at `n`
	- add 0 and n to the cuts array to treat them as boundaries for easier computation

2. Sort the cuts
	- sorting ensures that subproblems (segments) can be analyzed in a structured way

3. Define a DP table
	- create a 2D DP table `dp[i][j]` where:
	- dp[i][j] represents the minimum cost to cut the stick between cuts[i] and cuts[j]
	- set all values in `dp[i][j]` to `0` for segments where `j - i <= 1`(no cuts needed between adjacent cuts)
		- do we set the size of the matrix to something before initializing?

4. Iterate over segments lengths
	- solve subproblems in increasing order of segment length, starting from 2
		- segment length is the number of cuts in the segment plus 2 (accounting for the added boundaries)
	- for each segment `[cuts[i], cuts[j]]`:
		1. compute the cost to cut this segment
		2. divide the segment into two smaller subproblems at every possible cut `cuts[k]` where (i < k < j)
		3. use the formula 
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cost of cutting this segment)
			the cost of cutting this segment is cuts[j] - cuts[i]

5. Base case
	- if there are no valud cuts between cuts[i] and cuts[j], the cost is 0

6. Build the DP table
	- use nested loops
		1. outer loop to iterate over the length of the segment
		2. middle loop to iterate over the starting position i of the segment
		3. inner loop to iterate over the cut positions k within the segment 

7. Final result
	- after filling the dp table, the solution to the original problem should be stored in dp[0][m-1]
	- where m is the size of the extended cuts array

⌛ Complexity Analysis

O(c^3)

💻 Implementation of Solution

int minCost(int n, vector<int>& cuts) {
    // Add the boundaries (0 and n) to the cuts array
    cuts.push_back(0);
    cuts.push_back(n);
    sort(cuts.begin(), cuts.end());
 
    int m = cuts.size();
    vector<vector<int>> dp(m, vector<int>(m, 0));
 
    // Solve the problem using bottom-up DP
    for (int len = 2; len < m; ++len) { // Length of the subproblem
        for (int i = 0; i < m - len; ++i) {
            int j = i + len;
            dp[i][j] = INT_MAX;
 
            // Try every possible cut between i and j
            for (int k = i + 1; k < j; ++k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cuts[j] - cuts[i]);
            }
        }
    }
 
    // The result is stored in dp[0][m-1], covering the entire stick
    return dp[0][m - 1];
}

Graph View