public static int RodCutBottomUp(int n, int[] p) {
		int[] 	s  =  new int[p.length+1];
		for (int i=0; i!=s.length; ++i)
			s[i]  =  Integer.MIN_VALUE;
		
		// base case and trivial case
		s[0]  =  0;
		s[1]  =  p[0];
		
		// build up the table
		for ( int i=2; i <= n; ++i ){
			int		max  =  Integer.MIN_VALUE;
			for ( int j=1; j <= i; ++j ) {
				max  =  Math.max( max, p[j-1] + s[i-j] );
			}
			s[i]  =  max;
		}
		return s[n];
	}