[백준 11048] 이동하기 (DFS, DP) (C/C++) (★)

#include <iostream>
#include <algorithm>
using namespace std;
 
int row, col;
int map[1010][1010];
int dp[1010][1010];
 
int dx[3] = {1, 0, 1}; 
int dy[3] = {0, 1, 1};  
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int DFS(int x, int y)
{
    if(x == row-1 && y == col-1)
    {
        return map[x][y];
    }
    
    if(dp[x][y] != -1)
    {
        return dp[x][y];
    }
    
    for(int i = 0; i < 3; i++)
    {
        int xpos = x + dx[i];
        int ypos = y + dy[i];
            
        if(safe(xpos, ypos) == 1)
        {
            dp[x][y] = max(dp[x][y], DFS(xpos, ypos) + map[x][y]);
        }
    }
    
    return dp[x][y];
}
 
int main(void)
{
//    freopen("B11048_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
            dp[i][j] = -1;
        }
    }
    
    cout << DFS(0, 0);
    
    return 0;
}