2020/07/06 공부 - dynamic programming

 backtrack을 끝내고 이제 DP를 해볼 차례다.

 DP는 원래 n square의 시간복잡도가 걸리는 일을 2가지 방법을 이용해 n에 linear하게 수행할 수 있도록 해주는 기법 중 하나이다. 이 2가지 방법은
 첫째, 현재의 state로 미래의 state를 계산해 주는 점화식
 둘째, 이미 계산했던 값이라면 계산했던 값을 사용하는 memoization
 두 가지를 사용한다.

 대표적으로 DP를 사용해서 시간을 줄일 수 있는 것이 조합이다. nCr에서 파스칼의 삼각형 특징을 이용해서 복잡한 계산을 조금 간단하게 줄일 수 있는데, 순열 점화식 

$_nC_0=_nC_n=1$
$_nC_r=_{n-1}C_{r-1}+_{n-1}C_r$
에서 2번째 점화식의 우항 부분이 계산되어 있다면 이를 저장해둔 후, 필요할 때 불러오는 방식을 사용한다.

 예제로 백준 2579번을 풀었다.

int dynamic_programming(vector<int>& point_per_stair, int N) {
	// memoization
	vector<int> dp(N);

	// 점화식의 초항
	dp[0] = point_per_stair[0];
	dp[1] = point_per_stair[0] + point_per_stair[1];
	dp[2] = point_per_stair[2] + max(point_per_stair[0], point_per_stair[1]);

	// 어떤 i번째 계단
	// i번째 계단을 계산하기 위해서는 i-1번째, i-2번째, i-3번째 계단까지 최댓값이 필요함.
	// 가능한 경우의 수; i, i-1, i-2는 존재하지 않음.
	// i번째 밟고 i-1번째 밟고 i-3번째 밟은 경우 (i-2번째 계단을 밟지 않아서)
	// i번째 밟고 i-2번째 밟은 경우

	for (int i = 3; i < N; i++) {
		dp[i] = max(dp[i - 3] + point_per_stair[i - 1] + point_per_stair[i], dp[i - 2] + point_per_stair[i]);
		// dp[i] = i번째 계단을 최종 계단으로 생각했을 때, 최대 점수
		// dp[i-3] = i-3번째 계단 밟았을 때 최고 점수
		// + point[i-1] + point[i] = i-3번째, i-1번째, i번째 계단 밟았을 때 점수
		// dp[i-2] = i-2번째 계단 밟았을 때 최고 점수
		// + point[i] = i-2번째 계단 밟고 i번째 계단 밟았을 때 점수
	}

	return dp[N-1];
}

 

 구현한 이유는 코드에 기술되어 있다. dp[i]는 i번째 계단을 최종 계단으로 생각했을 때, 그러니까 i번째 계단을 밟았을 때 최대 점수이다. 이 dp vector를 이용해서 점화식을 세울 수 있다. dp[i]의 특징을 이용하기 때문에 점화식이 한 줄로 나오게 된다.

 

void solve() {
	int N;
	cin >> N;
	vector<int> point_per_stair(N);
	for (int i = 0; i < N; i++) {
		cin >> point_per_stair[i];
	}

	cout << dynamic_programming(point_per_stair, N);
}