막대 자르기

길이가 n인 막대를 길이가 i, 1<=i<=n-1 인 조각으로 잘라서 팔려고 할 때 최대 판매 금액을 얻는 문제이다.
R(n)을 길이가 n인 막대에서 얻을 수 있는 최대 금액 이라고 했을 때 다음과 같이 표현할 수 있다.
R(n) = MAX( p1+R(n-1) , p2+R(n-2) ,,, pn-1 + R(1) + pn ) (n>=2)
R(1) = p1

이를 점화식으로 표현하면 다음과 같다.
R(n) = MAX(pi + R(n-i))

동적 계획 Dynamic Programming

public class Main
{
    public static int func_DC(int[] price, int n)
    { // 길이 n인 막대를 잘라 최대 가격  분할 정복으로 계산
        if (n==0) return 0;
        int maxSell = 0;
        for (int i=1; i<=n; i++)
        {
            maxSell = Math.max(maxSell, price[i-1] + func_DC(price, n-i));
        }
        return maxSell;
    }
    
    public static int func_DP(int[] price, int n)
    { // 동적 계획
        int[] maxSell = new int[n+1]; // 중복되는 값들 테이블에(배열) 저장
        maxSell[0] = 0; // R0 = 0
        for (int i=1; i<=n; i++)
        {
            int maxval = 0;
            
            for (int j=1; j<=i; j++)
            {
                maxval = Math.max(maxval, price[j-1] + maxSell[i-j]);
            }
            maxSell[i] = maxval;
        }
        
        for (int k=0; k<maxSell.length; k++)
        {
            System.out.println("maxSell[" + k + "] = " + maxSell[k]);
        }
        return maxSell[n];
    }
    
	public static void main(String[] args) {
	    
	    int[] arr = {4,5,9,10};
	    System.out.println(func_DC(arr, 3));
	    System.out.println(func_DP(arr, 3));
	}
}

시간 복잡도는 분할 정복일때 O(2^n), 동적 계획 DP일 때 O(n^2).
메모이제이션