baekjun 11048. 이동하기

 O(3^n) dp문제 - 근데

#include <bits/stdc++.h>
 
using namespace std;
int N,M;
int maze[1001][1001];
int cache[1001][1001];
 
int findMaze(int i, int j){
    if(i == N && j == M){
        return maze[i][j];
    }
    if(i > N || j > M){
        return 0;
    }
    if(cache[i][j]!=-1){
        return cache[i][j];
    }
    int &ret = cache[i][j];
    int result = findMaze(i + 1, j);
    result = max(result, findMaze(i + 1, j + 1));
    result = max(result, findMaze(i, j + 1));
    return ret = maze[i][j] + esult;
}
 
int main(){
    cin >> N >> M;
    memset(cache, -1, sizeof(cache));
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            cin >> maze[i][j];
    cout << findMaze(1, 1);
    return 0;
}
 

#include <bits/stdc++.h>
 
using namespace std;
int maze[1001][1001];
int d[1001][1001];
int N,M;
 
int main(){
    cin >> N >> M;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            cin >> maze[i][j];
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            d[i][j] = max(d[i][j-1], d[i-1][j]) + maze[i][j];
            // d[i][j] + d[i+1][j+1] <= d[i][j] + d[i][j+1] + d[i+1][j+1] if maze[x][y] >=0
        }
    }
    cout << d[N][M] << endl;
    return 0;
}
 

*d[i][j] + d[i+1][j+1] <= d[i][j] + d[i][j+1] + d[i+1][j+1] if maze[x][y] >=0