프로그래머스 - 땅따먹기[Java]

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

 

이 문제에서 가장 중요한점은 dp배열을 이용하여 각 위치에서 내려갈때 최대값을 저장하고 그 값들을 이용하여 중복 계산을 방지하는 것이다.

 

 

 

import java.util.*;

class Solution {
    public static int answer = 0;
    public static int[][] dp;
    int solution(int[][] land) {
        
        dp=new int[land.length][land[0].length];
        
        for(int[] row : dp){
            Arrays.fill(row,-1);
        }
        
        int answer = 0;
     
        for (int i = 0; i < 4; i++) {
            answer = Math.max(answer, dfs(land,i, 0));
        }
        
        return answer;
    }
    
    public int dfs(int[][] land, int w, int h){
        
        if(h==land.length-1){
            return land[h][w]; //가장 마지막행에 도달하면 더이상 내려갈 수 없으므로 현재 위치의 값을 반환
        }
        if(dp[h][w]!=-1){
            return dp[h][w]; //전에 계산했던 값을 이용하여 최대값 반환
        }
        int max = Integer.MIN_VALUE;
        for(int i=0; i<4; i++){
            if(i!=w){ //바로 아래는 방문 못하므로 조건을 걸어줌
                max=Math.max(dfs(land,i,h+1),max);
            }
        }
        return dp[h][w]=max+land[h][w];
    }
}