Dynamic programming

Dynamic programming에는 2가지 방식으로 사용할 수 있습니다.

• Top down 방식
• Bottom-Up 방식

둘 중 더 많이 사용되고 범용성이 좋은 방식은 Top down 방식 입니다.

1) Top down 방식

작동 방식

다음과 같이 첫줄에는 높이와 넓이가 입력되고, 다음으로는 높이와 넓이 만큼의 배열에 들어갈 value 값들이 입력된다.
입력된 value 값들은 모두 점수로 (0,0) 즉 좌상단에서 시작하여 입력된 높이까지 도달하게 될 때 최대점수는 몇점인지 출력해보려고 합니다.
높이가 낮아질 때 마다 움직일 수 있는 범위는 바로 밑, 좌하 1칸, 우하 1칸 이렇게 3가지 경우입니다.

>> 입력 값			
7 3
1 0 0
1 2 2
0 3 0
3 -10 -5
15 -10 50
15 -10 10
0 6 4

#include <iostream>
using namespace std;

int height, width;
int MAP[1001][1001];

// dynamic programming 핵심
// 기록을 통한 재계산 방지
// row,col로부터 끝까지 갔을 때의 점수
int dp[1001][1001];


int dfs(int row, int col) {
	// 조건 : 맨 아래 도착시 끝
	if (row >= height - 1) {

		return MAP[row][col];
	}
	// dp에 계산했던 기록이 있으면 다시 계산 할 필요없이 return
	if (dp[row][col] != -2134567890) return dp[row][col];
	

	int nowScore = 0;
	int maxNextScore = -999;

	// 좌하,하,우하 
	int dr[] = { 1,1,1 };
	int dc[] = { -1,0,1 };
	for (int i = 0; i < 3; i++) {

		int nextRow = row + dr[i];
		int nextCol = col + dc[i];

		// 배열을 벗어나지 않도록 방지
		if (nextCol < 0 || nextCol >= width) continue;
		// 0을 벽으로 취급하기 때문에, 벽 회피
		if (MAP[nextRow][nextCol] == 0) continue;

		// 다음 좌표의 점수들을 얻어오기
		int nextScore = dfs(nextRow, nextCol);
		// 3방향에서 얻어온 점수들 중 가장 높은 점수
		if (maxNextScore < nextScore)
			maxNextScore = nextScore;
	
	}
	nowScore = maxNextScore + MAP[row][col];
	dp[row][col] = nowScore;
	return nowScore;
}


int main() {

	
	cin >> height >> width;
	// 넓이와 높이 만큼 배열에 입력 받기
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cin >> MAP[i][j];
			// 값 초기화
			dp[i][j] = -2134567890;
		}
	}

	cout << dfs(0, 0);

	return 0;
}

모든 dfs에서 dynamic을 사용할 수 있는건 아니다
저장이 사용해서 가능한면 dynamic 사용 가능

Dynamic Programming 설계 방법
1) dp[][] : index - 변인 요인, value - 구하고자 하는 값(해당 변인 요인에서'부터' 최종 상태까지 결과값)
2) now -> next 구조 생각하기
3) 반환 받으면서 처리
4) dp[now]로 계산한 결과를 저장

2) Bottom-Up 방식

#include <iostream>
using namespace std;

int height, width;
int MAP[1001][1001];

// dynamic programming 핵심
// 기록을 통한 재계산 방지
// row,col로부터 끝까지 갔을 때의 점수
int dp[1001][1001];


// for문 방식, 각 level 별로 시작'부터' 채워나가는 방식
int bottom_up() 
{
	// 초기는 이전 값이 없으므로 직접세팅
	int nowScore = 0;
	dp[0][0] = MAP[0][0];
	for (int row = 1; row < height; row++) 
	{
		for (int col = 0; col < width && col <= row; col++) 
		{
			if (MAP[row][col] == 0) continue;
			// row, col을 지금 now라고 생각하기, 
			// 결과값 : now'까지'의 최대 점수
			int dr[] = {-1,-1,-1};
			int dc[] = {-1,0,1};

			
			int maxPrevScore = -999;
			
			for (int i = 0; i < 3; i++)
			{
				int prevRow = row + dr[i];
				int prevCol = col + dc[i];
				if (prevCol < 0 || prevCol >= width) continue;
				if (maxPrevScore < dp[prevRow][prevCol])
					maxPrevScore = dp[prevRow][prevCol];
			}
			nowScore = maxPrevScore + MAP[row][col];
			dp[row][col] = nowScore;
			
			
		}
	}
	return nowScore;
}


int main() {

	
	cin >> height >> width;
	// 넓이와 높이 만큼 배열에 입력 받기
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cin >> MAP[i][j];
			// 값 초기화
			dp[i][j] = -2134567890;
		}
	}

	cout << bottom_up();


	return 0;
}

bottom-up 방식 : now'까지'결과 for문 now에서 prev에 초점
명확한 순서가 정해지지 않을 수 가 있다.
top down 방식 : now'부터' 결과 dfs now에서 next에 초점, 모든 경로에 대하여 계산