class Solution{

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

public static int bestPrice[] = new int[price.length] ;

public static void main(String args[]){

     if( price.length >= 2 ){
        calculateprice(price.length-1) ;
        System.out.println( "Best price that can be attained for rod of length " + (price.length - 1 ) + " is " + bestPrice[price.length - 1] );
     }
}

public static void calculateprice(int len){

    System.out.println( len );

    if( len == 1 ){
        bestPrice[1] = price[len] ;
        return;
    }

    int currentBestPrice = price[len] ;
    for( int i = 1 ; i <= len/2; i++ ){

        if( bestPrice[i] == 0 )
            calculateprice(i) ;
        if( bestPrice[len-i] == 0 )
            calculateprice(len-i)  ;

        currentBestPrice = Math.max( currentBestPrice , bestPrice[i] + bestPrice[len-i] ) ;
    }
    bestPrice[len] = currentBestPrice ;
    return ;
}