Skills101
← All coding problems

Rod Cutting

easyDynamic Programming II+10 XPTime limit 2s

A carpenter has a wooden rod of length n. A piece of length i sells for price[i] rupees. She may cut the rod into any number of pieces of whole lengths (or not cut it at all). What is the most money she can earn?

Input:

  • line 1: n
  • line 2: n prices — price[1] … price[n]

Output: the maximum total price.

Constraints: 1 ≤ n ≤ 1000, 0 ≤ price ≤ 10⁶. The answer fits in a 64-bit integer.

Think about it: decide the first piece: if it has length k, the rest is the same problem for length n − k. So best[L] = max over k of price[k] + best[L − k], filled for L = 1 … n. O(n²).

Sample input 1

8
1 5 8 9 10 17 17 20

Sample output 1

22

Sample input 2

4
3 5 8 9

Sample output 2

12

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.