백준_11048_이동하기 / DP**

허허허허허

이전꺼(목장 건설하기) 풀고 지금꺼(이동하기) 푸니까

쉽다면서 풀었는데 

틀렸다 ㅎ허허허허허허

나 이런 문제 풀었엇는데 ㅠㅠㅠㅠ

뭐 배열 하나 더 만들어서,,, 그 저장하고,,어쩌구,,,허허,,, 풀기싫다,,,

메모리초과 -> 완전탐색으로 풀었기때문이지!

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N, M; // 미로 크기 (N,M)

int getMostCandies(vector<vector<int>> _arr, 
					int _x, int _y, // 현재위치 x,y
					int _sum)      // 여기까지(현재위치빼고) 오는데 합한 사탕의 수
{   
	int sum = _sum + _arr[_x][_y];
	if (_x==(N-1) && _y==(M-1)) { // 탈출조건
		return sum;
	}

	int sum_h, sum_u, sum_d;
	if (_x+1<N && _y<M) { // 하
		sum_h = getMostCandies(_arr,_x+1,_y,sum);
	}
	if (_x<N && _y+1<M) { // 우
		sum_u = getMostCandies(_arr, _x, _y+1, sum);
	}
	if (_x + 1<N && _y+1<M) { // 대각선
		sum_d = getMostCandies(_arr, _x + 1, _y+1, sum);
	}

	// 하,우,대각선으로 다 갔을 때 
	// 가장 사탕의 합이 큰 것
	sum = max(sum_h,sum_u);
	sum = max(sum,sum_d);
	
	return sum;
}

int main() {
	
	cin >> N >> M;
	
	// arr[N][M]
	vector< vector<int>> arr(N, vector<int>(M, 0));

	for (int x = 0; x < N; x++) {
		for (int y = 0; y < M; y++) {
			cin >> arr[x][y];
		}
	}

	int sum;
	
	sum = getMostCandies(arr,0,0,0);

	cout << sum << endl;
	return 0;
}