427-动态规划算法-斐波那契数列-蒲公英云

427-动态规划算法-斐波那契数列

你的名字 2022-09-05 04:27 276阅读 0赞

动态规划算法求解斐波那契数列

在这里插入图片描述
状态：dp数组，存储已经求解的子问题的最优解

递归版本的动态规划算法

//参数n表示斐波那契数列中数字的个数。
//返回相应个数的斐波那契数列数字的值。
int fabnacci(int n, int dp[]) 
{
    if (dp[n] > 0) 
    {
     //表示：子问题n之前被求解过了
        return dp[n];//直接返回解，提高算法的效率
    }
    if (n == 1 || n == 2) 
    {
        dp[n] = 1;
        return 1;
    }
    else 
    {
        dp[n] = fabnacci(n - 1, dp) + fabnacci(n - 2, dp);
        return dp[n] ;
    }
}
int main()
{
    //  1 1 2 3 5
    int n = 10;    
    int *dp = new int[n + 1]();
    int val = fabnacci(n, dp);
    cout << val << endl;
    return 0;
}

非递归版本的动态规划算法

在这里插入图片描述

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    const int n = 10;
    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];
    }
    cout << dp[n] << endl;
    return 0;
}