dp 기본문제

아래 줄로 내려 왔을때 최대 값을 출력하는 문제 ?

이 문제는 DP 로 접근을 해야한다 

int N;

int board[10][10];
int cache[10][10];


//dp (y,x) --> board[y][x] + max(dp(y+1, x), dp (y+1, x)) 


int dp(int y, int x){

	if (y == N - 1)
		return board[y][x];


	int &ret = cache[y][x];
	if (ret != -1)
		return cache[y][x];


	ret = board[y][x] + max(dp(y + 1, x), dp(y + 1, x + 1));

	return ret;
	
}
int main(void) {


	int TC = 1;
	int i;
	int max = 0;

	freopen("input7.txt", "r", stdin); setbuf(stdout, NULL);
	cin >> N;
	for (int i = 0; i < N; i++)
	for (int j = 0; j < i+1; j++)
		cin >> board[i][j];

	memset(cache, -1, sizeof(cache));

	cout << dp(0, 0) << endl;
	return 0;
}

2
41	32
23	4	1
4	3	5	17
28	19	19	17	14