Baekjoon - Climbing Stairs

Baekjoon : Climbing Stairs

Description

Given a stair S with a point on each floor, return the maximum score after climbing to the top of the stairs.

Rule of the Game

1. You can either climb a stair or two stairs at a time
2. You can not climb three stairs row, however the starting stair is not included
3. You must reach the the last stair

Examples

Input

6 // Number of the Stairs
10
20
15
25
10
20

Output

75
// 10 + 20 + 25 + 20

Approach

By using a dynamic programming, make an additional array of containing the possible maximum values after climbing the n-th step.
(i.e. - dp[i] = MAX(dp[i-2] + stairs[i], stairs[i-1] + stairs[i] + dp[i-3]);)

Solutions (C++)

#include <iostream>
using namespace std;

int N; 
int stairs[301];
int dp[301];

int MAX(int a, int b)
{
    return a > b ? a : b;
}

int main()
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> stairs[i];
    }

    dp[0] = stairs[0];
    dp[1] = MAX(stairs[0], stairs[0] + stairs[1]);
    dp[2] = MAX(stairs[0] + stairs[2], stairs[1] + stairs[2]);

    for (int i = 3; i < N; i++)
    {
        dp[i] = MAX(dp[i-2] + stairs[i], stairs[i-1] + stairs[i] + dp[i-3]);
    }
    
    cout << dp[N-1];
}