1736번: 쓰레기 치우기

https://www.acmicpc.net/problem/1736

$O(nm)$

다음 문제를 DP로 푼다.

1. 가장 오른쪽 위에서 왼쪽 혹은 아래로 이동한다.
2. 같은 행, 열에서는 최대 하나의 쓰레기를 수거할 수 있다.
위 조건을 만족하며 수거 가능한 쓰레기 수의 최댓값을 구하여라.

#include<cstdio>
#include<algorithm>
using namespace std;
int dp[101][101], n, m;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = m; j; j--) scanf("%d", dp[i] + j);
        for (int j = 1; j <= m; j++) dp[i][j] = max({ dp[i - 1][j],dp[i][j - 1],dp[i - 1][j - 1] + dp[i][j] });
    }
    printf("%d", dp[n][m]);
    return 0;
}