[C++] DP(Dynamic Programming)

📕 DP

하나의 문제를 작은 문제로 나누어 풀고 결합하여 해결하는 방법

✔ 전제 조건

1. 같은 규칙으로 계산해 나가야 한다.
2. 한 번 계산한 결과가 바뀌지 않아야 한다.

✔ 해결 방법

1. 상황을 설명할 수 있는 변인 요인 찾기
2. 배열 설정(변인 요인 n: n차원)
3. 규칙 찾기

배열의 합 구하기

int arr[10] = {1, 2, 3, 4, 5, 6, 7,  8, 9, 10};
for (int index = 0; index < 10; index++){
	for (int i = 0; i < index; i++){
    	prefix[index] += arr[i];
    }
}
---
DP
prefix[0] = 1;
for (int i = 1; i<10; i++){
	prefix[i] = prefix[i-1] + arr[i];
}
     

---

📝 구현 방법

✔ Bottom-Up

• 가장 작은 문제부터 진행
• 반복문으로 구현

✔ Top-down

• 가장 큰 문제부터 진행
• 시작에서 끝 갔다가 끝에서 다시 return 해온다.
• 재귀 호출(dfs)로 구현

Bottom-Up과 Top-down 둘 다 각각의 장단점이 있기에 어떤 방법이 더 좋다고 말할 수 없다.

(DP에서 초기값은 계산상 "절대 나올 수 없는 수" 설정)