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

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

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

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**状态：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;
    }

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

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#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;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/3417e8c9029f495a8db6d961d5f3cd07.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/d40fa42cf7d34ec1bf85ebeb674cc2fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/9092e301c6114a67adc7114806b9f467.png