# Wood Cutting

There is a wooden stick with length L >= 1, we need to cut it into pieces, where the cutting positions are defined in an int array A. The positions are guaranteed to be in ascending order in the range of \[1, L - 1]. The cost of each cut is the length of the stick segment being cut. Determine the minimum total cost to cut the stick into the defined pieces.

**Examples**

* L = 10, A = {2, 4, 7}, the minimum total cost is 10 + 4 + 6 = 20 (cut at 4 first then cut at 2 and cut at 7)

**Solution:** 2D DP 

**Key insights**:

1. left stick does not affect right stick
2. Treat the cuts as segments, account for indexes only
3. Treat as merging problem

**Base Case**:

Adjacent index can not be cut further, thus = zero

**Inductive Rule:**

1. Iterate through all possible merge locations of current segment length
2. Cost of current merge = Length of substick created + left stick creation cost + right stick creation cost

ex: 4 index stick

**--- -**

**-- --**

**- ---**

```
public class Solution {
  public int minCost(int[] cuts, int length) {    
    //sanity check
    if (cuts.length == 0 || length <= 0) return 0;

    //add 0 and Length cut to cuts
    List<Integer> arr = new ArrayList<>();
    arr.add(0);
    for (int x: cuts){
      arr.add(x);
    }
    arr.add(length);

    int[][] M = new int[arr.size()][arr.size()];

    //Base Cases: adjacent indexes cost 0, cant be cut
    for (int i = 0; i < arr.size() - 1; i++){
      M[i][i + 1] = 0;
    }

    //{0,2,4,7,10}
    //size = 5
    //greatest substick = 4

    int offset = 2; //substick lengths we are calculating
    while(offset < arr.size()){ //stop if more substicks than elements in cuts
      for(int left = 0; left + offset < arr.size(); left++){ //left index of substick
        int right = left + offset;
        Integer min = Integer.MAX_VALUE; //min cost of M[left][right]
        int mergeCost = arr.get(right) - arr.get(left);

        for (int k = left + 1; k < right; k++){
          int leftCost = M[left][k];
          int rightCost = M[k][right];
          int curCost = leftCost + rightCost;
          if (curCost < min){
            min = curCost;
          }
        }

        M[left][right] = mergeCost + min;
      }

      offset += 1;
    }
    
    return M[0][arr.size() - 1];
  }
}

```

Time Complexity: O(N \* N / 2) tiles to fill \* O(N) check merges = O(N^3)&#x20;

Space Complexity:  M\[ ] = O(N \* N) = O(N^2)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://llssff.gitbook.io/coding-problems/dynamic-programming/wood-cutting.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.