資訊之芽 動態規劃 Ex2. 塗色問題

#include <iostream>
using namespace std;
unsigned long long int F[1000001][3];
unsigned long long int f1(unsigned long long int m){
    F[1][0]=1;
    F[1][1]=1;
    F[1][2]=1;
    
    for (unsigned long long int n=2;n<=m;n++){
        F[n][0] =F[n-1][0]+F[n-1][1]+F[n-1][2];
        F[n][1] =F[n-1][1]+F[n-1][2];
        F[n][2] =F[n-1][0]+F[n-1][2];
        //cout << F[n][0]+ F[n][1]+ F[n][2] << ",";
        
    }
    return  F[m][0]+ F[m][1]+ F[m][2];
}
//https://oeis.org/A095263
unsigned long long int G[1000001];
unsigned long long int f2(unsigned long long int m){
    G[1]=3;
    G[2]=7;
    G[3]=16;
    
    for (unsigned long long int n=4;n<=m;n++){
        G[n]=3*G[n-1]-2*G[n-2]+G[n-3];
    }
    return G[m];
    
}

int main(int argc, const char * argv[])
{
    unsigned long long int m;
    cin >> m;
    cout << f1(m) << endl;
    cout << f2(m) << endl;
    return 0;
}