도둑질.md

코드

import java.util.*;

class Solution {
    public int solution(int[] money) {
        // dp배열에 들어갈 수 있는 최대 값이 5억 이므로 int 배열 선언
        // 첫번째 집을 털고 마지막 집을 안터는 경우
        int[] dp1 = new int[money.length];
        // 첫번째 집을 안털고 마지막 집을 터는 경우
        int[] dp2 = new int[money.length];
        
        dp1[0]=money[0];
        dp1[1]=Math.max(money[0],money[1]);
        for (int i=2; i<money.length-1; i++){
            dp1[i]=Math.max(dp1[i-1],dp1[i-2]+money[i]);
        }
        
        dp2[1]=money[1];
        for (int i=2; i<money.length; i++){
            dp2[i]=Math.max(dp2[i-1],dp2[i-2]+money[i]);
        }
        
        return Math.max(dp1[money.length-2], dp2[money.length-1]);
    }
}