白俊2579号:階段を上る

問題の説明

これは、

のルールに従って数値を追加して最大値を作成する問題です.

ルール:3つの連続値を選択できません.

方法

ある階段に着いたときに私たちに与えられた状況は2種類あります.

の不連続な階段です.

連続の階段です.

pseudocode

A(n)=Max(A(n,1),A(n,2))A(n) = Max(A(n,1),A(n,2))A(n)=Max(A(n,1),A(n,2))
A(n,1)=Max(A(n−2,1),A(n−2,2))+VnA(n,1) = Max(A(n-2,1),A(n-2,2))+VnA(n,1)=Max(A(n−2,1),A(n−2,2))+Vn
A(n,2)=A(n−1,1)+VnA(n,2) = A(n-1,1)+VnA(n,2)=A(n−1,1)+Vn

正解

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		if (N == 1) {
			System.out.println(arr[N - 1]);
		} else {

			int[][] dp = new int[2][N];
			dp[0][0] = arr[0];
			dp[0][1] = arr[1];
			dp[1][1] = dp[0][0] + arr[1];
			for (int i = 2; i < N; i++) {
				dp[0][i] = Math.max(dp[1][i - 2], dp[0][i - 2]) + arr[i];
				dp[1][i] = dp[0][i - 1] + arr[i];
			}
			System.out.println(Math.max(dp[0][N - 1], dp[1][N - 1]));
		}

	}
}