Answer: CRED SDE OA (2023) | Interval Dynamic Programming Optimization and Cost Minimiza

Approach This is a classic Interval Dynamic Programming problem. A greedy approach does not work because making a cut changes the sizes of future stick segments and therefore affects future costs. Instead, we solve every interval independently and combine the results. Key Observation Suppose we have: n = 7 cuts = [1,3,4,5] Add boundaries: [0,1,3,4,5,7] If we want to solve the interval: (0,7) we can choose any cut inside it as the first cut. For every possible first cut: cost ...