https://www.acmicpc.net/problem/11048
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
int board[1001][1001],dp[1001][1001];
int main() {
fastio;
int n,m; cin >> n >> m;
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> board[i][j];
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){
dp[i][j] = max({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + board[i][j];
}
cout << dp[n][m] << "\n";
return 0;
}
가져갈 수 있는 사탕의 "최댓값"을 가져가야 하고, 이동은 (r + 1,c),(r,c + 1),(r + 1,c + 1) 이렇게 3방향으로 이동을 할 수 있다고 하였으니 최댓값을 가져가기 위해선 max(3방향 중에서 가장 큰 값) + (현재까지 가져온 사탕의 수) 이렇게 세울 수 있습니다 따라서 dp식은
dp[i][j] = max({dp[i - 1][j],dp[i][j - 1],dp[i - 1][j - 1]}) + board[i][j] 이렇게 세울 수 있습니다.