알고리즘 - 땅따먹기

문제

• 링크

코드

function solution(land) {
    
    const test1 = (i,a,b,c,d) => {
        land[i][a] += Math.max(land[i-1][b], land[i-1][c], land[i-1][d]);
    }
    
    const test = () => {  
        
         for(let i = 1; i < land.length ; i++) {
            test1(i,0,1,2,3);
            test1(i,1,0,2,3);
            test1(i,2,0,1,3);
            test1(i,3,0,1,2);
        }
        
        let val = land[land.length-1];
        return Math.max(...val);
    }
 
    return test();
}

• 아는 분의 코드 : DP가 이해가 안 되어서

import java.util.*;
class Solution {

    // static int dp[][];
    static int dfs(int[][] land, int r, int c, int[][] dp){
        if(r == land.length){
            return 0;
        }
        else {
            if(dp[r][c] != -1){
                return dp[r][c];
            }
            int result = 0;
            for(int i = 0; i < 4 ; i++){
                if(i == c){
                    continue;
                }
                else {
                    result = Math.max(result, dfs(land,r+1,i,dp));
                }
            }
            result+=land[r][c];
            dp[r][c] = result;
            return result;
        }
    }
    int solution(int[][] land) {
        int answer = 0;
        int [][]dp = new int[land.length][4];
        for(int i = 0 ; i < land.length ; i++){
            Arrays.fill(dp[i],-1);
        } 
        for(int i = 0 ; i < 4 ; i++){
            answer = Math.max(dfs(land,0,i,dp), answer);
        }
        return answer;
    }
}

회고

• DP에 대한 기본 이해가 부족

• 비슷한 문제들을 풀어 보면서 감을 다시 익혀보자

  • 올해 목표 : DP를 극복해보자!