#3857

Minimum Cost to Split into Ones

pupil · 425 · lc medium +25 · 83.2% accepted · 44 likes · top 95%

⚑ Linear 1D DP

Description

Given a positive integer n, you can split any integer x into two positive integers a and b with a + b = x at a cost of a * b. Using repeated splits, reduce n all the way down to n individual ones. Return the minimum total cost to accomplish this.

Code

1
2
3