带备忘录和dp的递归

备忘录算法

代码语言：javascript复制

#include <iostream>
#include <vector>

using namespace std;

int helper(vector<int> &m, int n);
int fib(int n);

int fib(int n)
{
    if(n < 1)
    {
        return 0;
    }
    vector<int> m(n   1, 0);
    return helper(m, n);
}

int helper(vector<int>&m, int n)
{
    if(n == 1 || n == 2) 
    {
        return 1;
    }
    if (m[n] != 0)
    {
        return m[n];
    }
    m[n] = helper(m, n - 1)   helper(m, n - 2);
    return m[n];
} 

int main()
{
    int n;
    cin >> n;
    cout << fib(n);
    return 0;
}

dp数组迭代

代码语言：javascript复制

#include <iostream>
#include <vector>

using namespace std;

int fib(int n);

int fib(int n)
{
    if(n < 1)
    {
        return 0;
    }
    vector<int> dp(n   1, 0);
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= n; i  ) 
    {
        dp[i] = dp[i - 1]   dp[i - 2];
    }
    return dp[n];
}

int main()
{
    int n;
    cin >> n;
    cout << fib(n);
    return 0;
}

空间优化

代码语言：javascript复制

#include <iostream>

using namespace std;

int fib(int n);

int fib(int n)
{
    if (n == 1 || n == 2)
    {
        return 1;
    }
    int a, b, sum;
    a = b = 1;
    for (int i = 3; i <= n; i  ) 
    {
        sum = a   b;
        a = b;
        b = sum;
    }
    return sum;
}

int main()
{
    int n;
    cin >> n;
    cout << fib(n);
    return 0;
}

dp 数组 算法 优化

0 人点赞