백준 21923 곡예 비행 혼내주기

 

오랜만에 푸는 dp!
대부분 dp는 탑다운으로 푸는데 원래 바텀업에 비해 느리기도 하고 이 문제는 예외처리도 해줘야해서 마음에 안든다... 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(v) v.begin(), v.end()

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int arr[1005][1005], cache[1005][1005][2];
int n, m;

void input() {
    cin >> n >> m;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            cin >> arr[i][j];
        }
    }
}

int d(int x, int y, bool up) {

    int& ret = cache[x][y][up];
    if(ret != -1) return ret;

    int base = arr[x][y];

    if(x == n-1 && y == m-1 && !up) return base;

    ret = -1e9;
    if(up) {
        // R
        if(y+1 <= m-1)
            ret = max(ret, d(x, y+1, true) + base);

        // U
        if(x-1 >= 0)
            ret = max(ret, d(x-1, y, true) + base);

        // turn
        ret = max(ret, d(x, y, false) + base);
    } else {
        // R
        if(y+1 <= m-1)
            ret = max(ret, d(x, y+1, false) + base);

        // D
        if(x+1 <= n-1) 
            ret = max(ret, d(x+1, y, false) + base);
    }
    
    return ret;
}

int main() {
    fastio;
    input();
    memset(cache, -1, sizeof(cache));

    cout << d(n-1, 0, true);
    return 0;
}