[c++] 동적계획법(DP)

Bottom up 방식

#include<bits/stdc++.h>
using namespace std;
int dy[10];
int main() {
	ios_base::sync_with_stdio(false);
	ifstream cin;
	cin.open("input.txt");
	int n;
	cin >> n;
	dy[1]=1;
	dy[2]=2;
	for(int i=3; i<=n; i++){
		dy[i]=dy[i-1]+dy[i-2];
	}
	cout<<dy[7];
	return 0;
}

 

제일 작은 값을 구하고 그 값을 통해 다음값을 얻는 방식이다.

 

Top down 방식

#include<bits/stdc++.h>
using namespace std;
int dy[10];
int DFS(int x){
	if(dy[x]>0) return dy[x];
	if(x==1 || x==2) return x;
	else {
		return dy[x]=DFS(x-1)+DFS(x-2);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	ifstream cin;
	cin.open("input.txt");
	int n;
	cin >> n;
	cout<<DFS(n);
	return 0;
}

DFS를 통해 제일 큰값부터 접근하는 방법이다.

dy배열에 이미 값이 나온 것들은 저장하면서 진행되기 떄문에 실행시간을 줄일 수 있다.