땅따먹기

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

이전에 거의 같은 DP 문제를 풀었을때의 풀이가 기억이 나서 쉽게 풀 수 있었다

https://www.acmicpc.net/problem/1149

https://www.acmicpc.net/problem/2579

시간복잡도
O(NC^2)
100000 4 * 4

import java.util.*;

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int row = land.length;
        int col = land[0].length;

        int[][] dp = new int[row][col];
        
        for(int i = 0; i < col; ++i)
            dp[0][i] = land[0][i];
        
        for(int i = 1; i < row; ++i)
        {
            for(int j = 0; j < col; ++j)
            {
                int max = 0;
                for(int k = 0; k < col; ++k)
                {
                    if(j != k)
                        max = Math.max(max, dp[i-1][k]);
                }    
                dp[i][j] = max + land[i][j];
                //System.out.print(dp[i][j]);
            }
            //System.out.println();
        }

        for(int i = 0; i < col; ++i)
        {
            answer = Math.max(answer, dp[row-1][i]);
        }
        
        return answer;
    }
}