11048번: 이동하기

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


$O(nm)$

모든 사탕 개수는 음이 아니므로
dp[i][j]=max(dp[i-1][j],dp[i][j-1]) + a[i][j]
가 성립한다.
답은 dp[n][m]

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