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)

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