[11048] 이동하기

http://boj.kr/11048

기본 DP2.

D[i][j] : (1, 1) 에서 (i, j)으로 이동하면서 가져올 수 있는 사탕의 최대 갯수

< 소스코드 >

#include <stdio.h>
 
int g[1001][1001];
int d[1001][1001];
 
int go(int n, int m)
{
    int a, b;
    if(!n || !m) return 0;
    if(d[n][m] != -1) return d[n][m];
 
    a = go(n-1, m);
    b = go(n, m-1);
    return d[n][m] = (a > b ? a : b) + g[n][m];
}
 
int main()
{
    int i, j;
    int n, m;
    scanf("%d%d", &n, &m);
 
    for(i=1; i<=n; i++) {
        for(j=1; j<=m; j++) {
            scanf("%d", &g[i][j]);
            d[i][j] = -1;
        }
    }
 
    printf("%d\n", go(n, m));
    return 0;
}
 

>> go(n-1, m-1) 은 고려할 필요가 없다. 

< Bottom Up >

#include <stdio.h>
 
int n, m, g[1001][1001], d[1001][1001];
 
int main()
{
    int i, j, tmp;    
    scanf("%d %d", &n, &m);
 
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            scanf("%d", &g[i][j]);
 
    for(i=1; i<=n; i++) {
        for(j=1; j<=m; j++) {
            d[i][j] = g[i][j];
            tmp = d[i-1][j] > d[i][j-1] ? d[i-1][j] : d[i][j-1];
            d[i][j] += tmp;
        }
    }
    printf("%d\n", d[n][m]);
    return 0;
}