백준 알고리즘 DP ( 11052 번)

https://www.acmicpc.net/problem/11052

문제 해결

문제를 작은 문제로 쪼갤 수 있어야함

각각의 가격은 a(i)
n개의 가격의 최대값을 d(i)

n개의 가격의 최대값은
d(i) = MAX( a(j) + d(i-j) )

        for (int i=1; i<=n; i++) {
            for (int j=1; j<=i; j++) {
                if (d[i] < d[i-j] + a[j]) {
                    d[i] = d[i-j] + a[j];
                }
            }
        }

d[1] 부터 최대값을 저장해감
d[1]의 최대값은 d[0]+a[1]
d[2]의 최대값은 d[1]+a[1] 또는 d[0]+a[2]
d[3]의 최대값은 d[2]+a[1] 또는 d[1]+a[2] 또는 d[0]+a[3]
  .
  .
  .
d[n]의 최대값은 d[n-1]+a[1] ... d[0]+a[n] 중 하나