> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/dynamic-programming/buy-a-card.md).

# Buy a Card

아쉽게 틀린 문제 복기

다이나믹 프로그래밍 문제 풀이 방법

1. 다이나믹 프로그래밍은 작은 문제의 정답이 큰 문제의 정답으로 이어진다.
2. 쪼갤 수 없는 작은 문제로 쪼갠다.

d\[n]은 카드n개가 든 카드팩을 사는 최대 지불 비용이다. \
이것은 d\[n-1] + a\[1], d\[n-2] + 1\[2], ....이 될 수 있다. 이것을 점화식으로 나타내면

d\[i] = d\[i-j] + a\[j], (1<=j<=i)//여기서 코드로 구현할 때 i-j>=0으로 조건을 부여하는 것보다 j범위를 줄 때 j는 i만큼만 증가하기 때문에 1<=j<=i로 해주면 구현이 용이하다.

점화식 도출 성공. 이 점화식에서 모든 (i,j)쌍에 대한 최댓값 구하는 부분 생각 부족.\
\=> 대소 비교해서 더 크면 d\[i]값을 갱신하면 됨!(이 쉬운 걸 왜 놓쳤을까)\
d\[i]에서 i값에 따라 나오는 모든 경우의 수 값을 저장해야된다고 생각해서 2차원 배열이 필요하다고 생각했고, 그렇다면 d\[i]\[j]가 의미하는 바를 정의하는 데 어려움을 겪었음.

```java
for(int i=2;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];
				}
			}
		}
```