Cut Stick Cost Problem

Cut Stick Cost Problem — ExecCode Hard DSA Practice

Solve the Cut Stick Cost problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A stick of length n must be cut at given positions. Each time you cut a current piece, you pay the length of that whole piece (not the cut size). Order of cuts changes the total. This is the same DP as matrix-chain / burst balloons. Return the minimum total cost to perform every cut. You are given: n — stick length cuts — distinct cut positions strictly between 0 and n Return integer cost. If there is one cut at mid of n, you pay n once.

Examples

Input {'n': 7, 'cuts': [1, 3, 4, 5]}; Output 16. Input {'n': 9, 'cuts': [5, 6, 4, 7, 8]}; Output 21. Input {'n': 5, 'cuts': [1]}; Output 5

Constraints

Cuts can be done in any order You always pay the length of the segment you are currently cutting

Practice Cut Stick Cost free on ExecCode. Browse DSA problems, topic map, and placement guides.