介绍

今天，在本教程中，我们将讨论动态编程的概念。
这是一种更好的编程方法。

动态编程

从理论上讲，动态编程是一种解决问题的技术，它通过将问题分成子问题来解决。
当子问题相同且相互依赖时，动态编程就会出现。

它与解决问题的"分而治之"方法非常相似。
但是在某些情况下，分而治之技术可能多次执行某些操作或者任务(增加时间复杂度)。

因此，动态编程方法(DP)通常用于优化特定问题。

此外，DP遵循最优性原则，该原则指出，对于最优决策序列，每个子序列也必须是最优的。

示例–使用DP的斐波那契

现在我们已经讨论了动态编程的基本概念，让我们看一下如何使用这种方法解决问题。

在下面的示例中，我们尝试计算斐波那契数列中位置" n"(用户输入)处的数字。

如您所知，斐波那契数列看起来像这样，

0、1、1、2、3、5、8…最多n个词。

其中起始两位数字是0和1。

让我们编写一个程序，根据用户输入在斐波那契数列的特定点自动找到正确的数字。

使用递归(在C中)：

#include<stdio.h>
//fibonacci calculating function
int fibo(int n) 
{ 
	if(n==1)
		return 0;
	else if(n==2)
		return 1;
	else
		return fibo(n-1) + fibo(n-2); 
}
int main()
{
	int n,res;
	printf("Enter n : ");
	scanf("%d",&n);
	
	res=fibo(n);
	
	printf("fibo(%d) = %d",n,res);
	
	return 0;
}

输出：

Enter n : 5
fibo(5) = 3

斐波那契使用递归(如果n = 5)

如您所见，在我们上面的示例中，取n = 5，递归使用递归调用将问题分解为子问题。

仔细观察一下，请注意在这种情况下，fibo(3)被计算了两次。
然后分解为两个递归调用fibo(1)和fibo(2)。
它们的值分别为0和1。
最后，我们得到了期望的输出，即fibo(5)= 3。

应用DP(在C中)：

#include<stdio.h>

int fibo_series[100]; 

void set_zero()  
{  
  int i;  
  for (i = 1; i <= 100; i++)  
      fibo_series[i] = 0; 
}  
//fibonacci calculating function
int fibo(int n)  
{  
  if (fibo_series[n] == 0)  
  {  
      if (n <= 1)
          fibo_series[n] = n;  
      else
          fibo_series[n] = fibo(n - 1) + fibo(n - 2);  
	}  
	return fibo_series[n];  
}   
int main ()  
{  
  int n,res;  
  set_zero(); 
  
  printf("Enter n : ");
	scanf("%d",&n);
	
	if(n>=100 || n<=0)
		printf("Entered number is out of range!");
	else
	{
		res=fibo(n-1);
		printf("fibo(%d) = %d",n,res);
	}
	
	return 0;  
}

输出：

Enter n : 5
fibo(5) = 3

• 这次我们首先使用函数set_zero()初始化一个数组fibo_series []，该数组最多包含100个元素，其值为0。

• 一旦计算出此数组，该数组将进一步用于存储斐波那契数列的元素，

• 首先在fibo()函数内部，我们检查所需的元素是否已经计算并存储在数组中。
  如果不是，则进行计算。
  如果是，则将元素直接传递到函数调用的位置，

• 这样可以确保同一函数(如我们先前看到的fibo(3))不会被调用两次。
  因此，通过这种方式，我们获得了最佳解决方案。

注意：因为数组索引从零开始，所以我们在计算res时将(n-1)传递给函数fibo()。
鉴于我们正在考虑从索引1开始的系列元素。

出于相同的原因，我们使用了if-else语句来消除用户以" n> = 100"或者" n <= 0"输入n的情况。