C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 11048번:이동하기 답

//이동할때 오른쪽, 아래쪽, 오른쪽 아래 대각선 3가지 방법으로 이동할 수 있다.

//(i,j)로 이동할 때 최대값을 D[i][j]라 하면

//D[i][j] = max(D[i-1][j],D[i][j-1],D[i-1][j-1])+A[i][j]

#include <iostream>
#include <algorithm>
using namespace std;
int D[1001][1001], A[1001][1001];
int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> A[i][j];
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            D[i][j]=max(D[i - 1][j], max(D[i][j - 1], D[i - 1][j - 1])) + A[i][j];
    cout << D[N][M];
 
}