8. 땅따먹기 (프로그래머스)

가. 문제파악

 1. 유형 : DP

    -   많이보는 DP유형의 기본 문제, 점화식을 세우면 간단하게 해결된다.

 

나. 코드 

 1. 풀이 : DP

    -   해당라인을 밟는 최대값은 밟은 라인을 제외한 3개의 라인의 최대값이다.

    -   이를 누적해서 구하면 끝~

public class Solution {

    public int solution(int[][] land){

        int[][] dp = new int[land.length][land[0].length];
        dp[0][0] = land[0][0];
        dp[0][1] = land[0][1];
        dp[0][2] = land[0][2];
        dp[0][3] = land[0][3];
        for (int i = 1; i < land.length; i++) {
                dp[i][0]=Math.max(Math.max(dp[i-1][1],dp[i-1][2]),dp[i-1][3])+land[i][0];
                dp[i][1]=Math.max(Math.max(dp[i-1][0],dp[i-1][2]),dp[i-1][3])+land[i][1];
                dp[i][2]=Math.max(Math.max(dp[i-1][1],dp[i-1][0]),dp[i-1][3])+land[i][2];
                dp[i][3]=Math.max(Math.max(dp[i-1][1],dp[i-1][2]),dp[i-1][0])+land[i][3];
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < 4; i++) {
            max = Math.max(dp[land.length-1][i],max);
        }
        return max;
    }


    public static void main(String[] args) {
        System.out.println(new Solution().solution(new int[][]{{1,2,3,5},{5,6,7,8},{4,3,2,1}}));
       // System.out.println(new Solution().solution(new int[][]{{0,0,1,1},{1,1,1,1}}));
//        System.out.println(new Solution().solution(2,4,2,1));
    }
}