Rod cutting

Challenge

Implement:

int rod_cutting(const int *price, int n);

Return the maximum revenue obtainable by cutting a rod of length n, where price[k] is the price of a piece of length k+1.

Input format

price[0..n-1], rod length n.

Output format

Maximum revenue.

Constraints

Unbounded: each length may be cut many times.

Starter code

#include <stddef.h>
/* Max revenue cutting a rod of length n, where price[k] is the price of a piece of length k+1. */
int rod_cutting(const int *price,int n){ (void)price;(void)n; return 0; }

Common mistakes

Off-by-one indexing between piece length and its price index.

Edge cases to handle

Length 0 -> 0 revenue.

Background lessons

• Rod cutting & integer break