알고리즘
- (1,1)에서부터 순서대로 모든 점을 대상으로 visit (i -1, j), (i, j-1), (i-1,j-1) 이 가지고 있는 점 중 가장 큰 점을 visit(i,j) 에 저장한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
int visit[1010][1010], n, m, map[1010][1010];
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> map[i][j];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
visit[i][j] = map[i][j] + max(max(visit[i - 1][j], visit[i][j - 1]), visit[i - 1][j - 1]);
cout << visit[n][m];
}