private static int RodCutTopDownHelper(int n, int[] p, int[] s) {
		if ( s[n] != Integer.MIN_VALUE ) return s[n];
		
		// divide the problem into subproblem
		int		max  =  Integer.MIN_VALUE;
		for ( int i=1; i <= n ; ++i ) {
			// conquer each subproblem and combine them together
			max  =  Math.max(max, p[i-1]+RodCutTopDownHelper(n-i,p,s) );	
		}
		s[n]  =  max;
		return max;
	}