Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
Try to use dynamic programming where the current index and remaining number of line segments to form can describe any intermediate state.
To make the computation of each state in constant time, we could add another flag to the state that indicates whether or not we are in the middle of placing a line (placed start point but no endpoint).