フィボナッチ数列の記憶化探索と動的計画解法C++実現および関連事例分析(Leetcode 70-階段を登る)

フィボナッチ数列の記憶化探索と動的計画解法C++実現および関連事例分析(Leetcode 70-階段を登る)
Fibonacci数列の繰返し解析式:F(n)=F(n-1)+F(n-2)
一般的な最適化されていない解法

#include 
#include 
using namespace std;

int num=0;
int Fibonacci(int n)
{
    num++;
    if(n==1||n==2)
        return 1;
    return Fibonacci(n-1)+Fibonacci(n-2);
}
int main(int argc, char *argv[]) {
    int x=40;   
    x=Fibonacci(x);
    cout<return 0;
}

記憶化検索を使用して上から下へ最適化された解法

#include 
#include 
using namespace std;
vector<int> memo;
int num=0;
int Fibonacci(int n)
{
    num++;
    if(n==1||n==2)
        return 1;
    if(memo[n]!=-1)
        return memo[n];
    memo[n]=Fibonacci(n-1)+Fibonacci(n-2);
    return memo[n];
}
int main(int argc, char *argv[]) {
    int x=40;   
    memo = vector<int>(x+1,-1);
    x=Fibonacci(x);
    cout<return 0;
}

ダイナミックプランニングによるボトムアップ最適化の解法

#include 
#include 
using namespace std;
vector<int> memo;
int main(int argc, char *argv[]) {
    int x=40;   
    memo = vector<int>(x+1,-1);
    memo[0]=0;
    memo[1]=1;
    for(int i=2;i<=x;i++)
    {
        memo[i]=memo[i-1]+memo[i-2];
    }
    cout<return 0;
}

Leetcodeに関する問題
70. Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Example 1:

Input: 2
Output:  2
Explanation:  There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output:  3
Explanation:  There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

動的計画は記憶化探索と同様に0(n)の時間的複雑度であるが,動的計画は記憶化探索よりもやや速いため,この問題は直接動的計画で解き,フィボナッチ数列とほぼそっくりである.

class Solution {
public:
    int climbStairs(int n) {
    vector<int> memo = vector<int>(n+1,-1);
    memo[1]=1;
    memo[2]=2;
    for(int i=3;i<=n;i++)
    {
        memo[i]=memo[i-1]+memo[i-2];
    }
    return memo[n];
    }
};