嘡DP嘡Boottom Up嘡long型

質問する

リンク

に答える

1.問題のアクセスと解決ロジック

初期値
f(0)=0,f(1)=1f(0)=0,f(1)=1f(0)=0,f(1)=1

点火式
f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2)f(n)=f(n−1)+f(n−2)

2.コード

-Bootom Up(繰り返し文、星雲)

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

long long fibo[91];

// Bottm Up
int main(){
    
    fibo[0] = 0;
    fibo[1] = 1;
    
    int n;
    cin >> n;
    
    for(int i=2;i<=n;i++){
        fibo[i] = fibo[i-1] + fibo[i-2];
    }
    
    cout << fibo[n] << "\n";

    return 0;
}

🔥 データ型エラー

の先頭に立つ

int fibo[91];

と宣言し、問題を解いたが、幾何級数が増えたフィボナッチ数列の値をすべてintで表すことができなかったため、誤った答えが出た.

ジャッキー・チェンゴ

したがって,intより広い範囲のlong long型で代用する.

long long fibo[91];

4.時間複雑度分析

私たちはすべてのフィボナッチ数を救ったからです.
O(N)O(N)O(N)

5.問題の重要な部分

DP問題で重要なのは,点火式の導出である.
オプションはBootm Up(繰り返し文)で展開するか、Top Down(再帰)で展開するか