[yukicoder] No.45 回転寿司

No.45 回転寿司

No.45 回転寿司 - yukicoder

どうやって解くのか分からなかったので、解説をみました。どうやら動的計画法で解くようです。

解説を見て動的計画法ってこういう問題なんだと少しわかったような気がします。良い問題ですね。

mmxsrup.hatenablog.com

yukicoder No.45 - 回転寿司 - ゲームにっき（仮）別館（仮）

コード

import java.util.Arrays;
import java.util.Scanner;

public class Exec0045 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int []V = new int[N];
        for(int i = 0; i < N; i++) {
            V[i] = scan.nextInt();
        }
        scan.close();
        if(N == 1) {
            System.out.println(V[0]);
            System.exit(0);
        }
        int []dp = new int[N];
        Arrays.fill(dp, 0);
        dp[0] = V[0];
        dp[1] = Math.max(V[0], V[1]);
        for(int i = 2; i < N; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + V[i]);
        }
        System.out.println(dp[N - 1]);

    }
}