動的計画法part1

AtcoderさんのDPまとめコンテストのC問題　記録
今回はdpで最大値を求める問題。
それぞれのテーブルの値の最大値はどのように求められるのか意識してコードを書く必要がある。
この問題ではa,b,cは2回連続は使えない。

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int a[100000], b[100000], c[100000];
    for(int i = 0; i < n; i++){ 
        cin >> a[i] >> b[i] >> c[i];
    }

    int dp[3][100000];

    dp[0][0] = a[0];
    dp[1][0] = b[0];
    dp[2][0] = c[0];

    for(int j = 1; j < n; j++){
        dp[0][j] = max(dp[1][j-1],dp[2][j-1]) + a[j];
        dp[1][j] = max(dp[0][j-1], dp[2][j-1]) + b[j];
        dp[2][j] = max(dp[0][j-1], dp[1][j-1]) + c[j];
    }

    cout << max(dp[0][n-1], max(dp[1][n-1],dp[2][n-1]));
    return 0;
}