public class CutRod
{
    static int []price = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

    static int cut_rod(int n)
    {
        System.out.println("...cut_rod " + n);
        if (n == 0) 
            return 0;

        int best_price = 0;
        for (int i = 1; i <= Math.min(n, price.length - 1); i++)
            best_price = Math.max(best_price, price[i] + cut_rod(n - i));

        return best_price;
    }
}