[C++]BOJ 11048 - 이동하기

단순한 dp문제다. 문제의 이동 조건에서 (r+1, c), (r, c+1), (r+1, c+1) 이렇게 3가지를 제시했지만, 사실 상 마지막 (r+1, c+1) 은 신경쓰지 않아도 된다.
왜냐하면 사탕의 갯수는 0 이거나 양수이기 때문에 더 많은 사탕을 가져와야 될 판에 굳이 대각선으로 가로질러 올 필요가 없기 때문이다.

dp[i][j] 에 현재 칸 까지 가장 많이 가져올 수 있는 사탕의 갯수를 넣는다.
마지막에 dp[n][m] 을 출력한다.

#include <iostream>
using namespace std;
int n, m, dp[1001][1001];
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			cin >> dp[i][j];
			dp[i][j] += max(dp[i - 1][j], dp[i][j - 1]);
		}
	cout << dp[n][m];
}