隣接するコインを選択せずに最大化

6878 ワード
テキストリンク
お金を探す問題と同様に、動的な割り当てを使用して解決することができます.
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));
    }
}
隣接する2つの硬貨を選択できないため、例えば6個の硬貨の中で最大値を取らなければならない場合、5個の硬貨の中の最大値の結果、あるいは4個の硬貨の中の最大値の結果+6個の硬貨のようにdpで解決することができる.
ans[i] = Math.max(ans[i-1], ans[i-2] + coin[i])
略語に関するCSS(1行、2行)
MacBookのネジが固くて外れないと思ったら簡単に外れた話