[白俊]2003回フィボナッチ関数

1506 ワード
白駿 テキストリンク

[白俊]2003回フィボナッチ関数


質問リンク:https://www.acmicpc.net/problem/1003

質問する



にゅうしゅつりょく




質問へのアクセス


これはdp問題です.ルールを探せばいいです.私はそれをルールの下で解いた.0と1がそれぞれフィボナッチを構成しているからだ.しかし、他の人の解答を見ると、0と1を別々に考えるのではなく、フィボナッチ数列を一緒に考え、1出力dp[n]でいい、0出力dp[n-1]でいいことがわかります.

コード実装（C++）

#include <iostream>

using namespace std;
int cacheZero[41];
int cacheOne[41];
void cal(int num){
    for(int i = 2 ; i <= num ; i++){
        cacheZero[i] = cacheZero[i-1] + cacheZero[i-2];
        cacheOne[i] = cacheOne[i-1] + cacheOne[i-2];
    }
    cout << cacheZero[num] << " " << cacheOne[num] << "\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cacheZero[0] = 1; cacheZero[1] = 0;
    cacheOne[0] = 0; cacheOne[1] = 1;
    int testCase;
    cin >> testCase;
    int num;

    for(int i = 0 ; i < testCase ; i++){
        cin >> num;
        cal(num);    
    }
}
データインポートExcel,word
backjun-領域を求める(2583)