이웃한 동전을 선택하지 않고 최대로 가져가기

거스름돈 문제와 마찬가지로 동적 할당을 이용해서 해결할 수 있다.

public class Main
{ 
    public static int func(int[] coin)
    {
        int[] ans = new int[coin.length];
        ans[1] = coin[1];
        ans[2] = Math.max(coin[1], coin[2]);
        for (int i = 3; i<coin.length; i++)
        {
            ans[i] = Math.max(ans[i-1], ans[i-2] + coin[i]);
        }
        
        return ans[ans.length-1];
    }
    
    public static void main(String[] args)
    { // 편의를 위해 첫 원소를 0으로 함
        int[] coin = {0,5,1,2,10, 6, 3, 8, 1, 11, 14};
        System.out.println(func(coin));
    }
}

인접한 동전 두개를 선택할 수 없기 때문에 예를 들어 6개중 최대값을 내야 한다고 했을때 5개중 최대값 결과, 혹은 4개중 최대값 결과 + 6번째 동전 과 같은 식으로 dp를 이용해 해결할 수 있다.

ans[i] = Math.max(ans[i-1], ans[i-2] + coin[i])