ProDeveloperTutorial.com

教程和编程解决方案
菜单
  • Shell脚本
  • 系统设计
  • Linux系统编程
  • 4g LTE
  • 编码问题
  • C
  • C ++
  • DSA
  • GIT

动态编程简介与示例

前开发者教程 2019年8月18日

在本章中,我们将学习以下主题:

  1. 什么是动态编程
  2. 自上而下和自下而上的方法
  3. 记忆和表格方法。

 

在上一章中,我们研究了递归,并看到了递归树,如下所示:

 

recursion_tree

 

根据以上所述,时间复杂度将为2 ^ n,您仔细观察发现,我们对已经国彩网出的值重复进行国彩网。

 

我们多次国彩网“ fib(2)”,“ fib(1)”,“ fib(0)”的值。

 

那么有没有办法只国彩网一次呢?

 

是的,有办法。我们将已国彩网值的结果存储在数组中。

 

下次当我们尝试为已国彩网的值国彩网值时,我们将在数组中检查该值是否存在。如果存在,那么我们从数组中取出并使用它。否则,我们国彩网该值并将其存储在数组中以备将来使用。

 

由于我们将结果存储为已经国彩网出的值,因此可以在我们的问题中进一步使用它,称为动态编程。

 

dong动态编程有两种方法。

 

  1. 自上而下的方法/记忆
  2. 自下而上的方法/表格方法。

 

在讨论自顶向下和自底向上方法之前,让我们讨论动态编程的特征

 

动态编程的特点

DP有2个最重要的特征,它们是:

  1. 重叠子问题
  2. 最佳子结构属性

1.重叠子问题

一种。任何问题都可以分为子问题。

b。如果子问题重叠,即解决子问题涉及多次解决相同的子问题,则该问题将满足重叠子问题的条件。

例如:

对于斐波那契数列,找到fib(5),我们到达子问题树,如下所述。如果您看到fib(2)被多次国彩网,fib(1)也被多次国彩网。

recursion_tree

2.最佳子结构属性

在这种类型中,可以从一个简单的方程式得出解。

对于斐波那契数列:Fib(n)= Fib(n-1)+ Fib(n-2)

  1. 自上而下的方法/记忆

让我们通过使用相同的斐波那契数作为示例来了解这种方法:

 

在这种方法中,我们采用一个数组来存储先前国彩网出的值。

 

步骤1:取得阵列并以-1初始化。在国彩网fib(5)时,我们采用5元素数组。

 

动态编程简介与示例

 

首先我们国彩网“ fib(5)”。 fib(5)的值为-1,我们进一步国彩网,因此递归调用“ fib(4)”

 

动态编程简介与示例

 

检查4日 数组的索引为-1,递归调用“ fib(3)”

 

动态编程简介与示例

 

由于“ fib(3)”也是-1,因此再次递归调用“ fib(2)”。

 

动态编程简介与示例

 

由于“ fib(2)”也是-1,因此需要“ fib(1)”。

 

动态编程简介与示例

 

由于索引为“ 1”,因此我们返回1并用索引1的数组更新1。

 

动态编程简介与示例

 

同样,“ fib(2)”将称为“ fib(0)”。由于“ 0”将返回“ 0”,因此将更新阵列。

 

动态编程简介与示例

 

现在我们可以国彩网出fib(2)= fib(1)+ fib(0)= 1 + 0 = 1的值,将其更新为数组。

 

动态编程简介与示例

 

现在我们必须做2nd递归调用“ fib(3)”。

 

即“ fib(2)”。但是,由于我们已经知道数组中fib(2)的值,因此我们使用该值来国彩网fib(3)。

 

动态编程简介与示例

 

现在我们需要做2nd递归调用“ fib(4)”。

 

The 2nd对“ fib(4)”的递归调用是“ fib(2)”。我们知道fib(2)的值,我们可以国彩网“ fib(4)”的值并更新数组。

 

动态编程简介与示例

 

现在做2nd递归调用fib(5)。 2nd对“ fib(5)”的递归调用是“ fib(3)”。正如我们已经知道fib(3)的值,使用它并获得最终结果。

 

动态编程简介与示例

 

因此,如您所见,通过使用Memonization方法,我们通过使用动态编程将时间复杂度从2 ^ n降低到O(n);

 

并且,在这里我们从上到下解决了问题以获得结果。这称为自顶向下方法。我们已将中间结果存储在数组中。这称为记忆化技术。

 

C ++程序使用自上而下的方法和记忆技术来查找斐波那契数列。

 

#include<iostream>
using namespace std; 

int array_memo [6];  
  
int fib(int n)  
{  
    if (array_memo[n] == -1)  
    {  
        if (n <= 1)  
            array_memo[n] = n;  
        else
            array_memo[n] = fib(n - 1) + fib(n - 2);  
    }  
  
return array_memo[n];  
}  
  
int main ()  
{  
    int n = 5;  
    
    //initialize array to -1
    for(int i = 0; i < 6 ; i++)
        array_memo [i] = -1;

    cout << "Fibonacci number is " << fib(n)<<endl;  
    return 0;  
}  

输出:

Fibonacci number is 5

 

 

  1. 自下而上的方法/表格方法。

 

现在我们将学习自底向上或表格方法。

 

表格方法可以通过迭代方法而不是递归方法来实现。下面是用迭代方法国彩网斐波那契的函数。

 

int fib ( n)
{
	int arr[5]
	arr[0] = 0
	arr[1] = 1
	if (n <= 1)
		return n

	for(i = 2; i <= n ; i++)
	{
		arr[i] = arr[i-1] + arr [i -2]
	}

	return arr[n]
}

 

在上面的程序中,我们必须生成一个数组,然后我们将从低索引到高索引开始填充数组。当前两个索引被预填充时,我们将从

Pass 3:
arr [0]  = 0
arr[1] 	= 1
arr [2] 	= arr [0] + arr [1]
	= 1 + 0

arr[2] 	= 1	 

array:

0, 1, 1, 0, 0, 0

Pass 4:
arr [3] 	= arr [2] + arr [1]
	= 1 + 1

arr[2] 	= 2	 

array:

0, 1, 1, 2, 0, 0
Pass 4:
arr [4] 	= arr [3] + arr [2]
	= 2 + 1

arr[4] 	= 3	 

array:

0, 1, 1, 2, 3, 0
Pass 5:
arr [5] 	= arr [4] + arr [3]
	= 2 + 3

arr[4] 	= 5	 

array:

0, 1, 1, 2, 3, 5

 

在这里,如果您仔细观察,我们将从较低的索引填充到较高的索引。因此,它是使用表格方法的自下而上的方法。

 

使用表格技术查找斐波那契数列的C ++程序。

#include<iostream>

using namespace std;

int fib(int n) 
{ 
  int fib_arr[n+1]; 
  fib_arr[0] = 0;   
  fib_arr[1] = 1; 

  for (int i = 2; i <= n; i++) 
      fib_arr[i] = fib_arr[i-1] + fib_arr[i-2]; 
  
  return fib_arr[n]; 
} 
   
int main () 
{ 
  int n = 5; 
  cout<<"Fibonacci number is = "<<fib(n)<<endl; 

  return 0; 
}

 

输出:

Fibonacci number is = 5

进一步阅读:

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

 

 

该网站上可用的教程列表:

C编程20+章C ++编程80+章
100多个编码问题数据结构和算法85+章
系统设计20+章Shell脚本编写12章
4g LTE 60+章节最常见的编码问题
5G NR 50+章Linux系统编程20+章
分享
电子邮件
鸣叫
领英
Reddit
绊倒
Pinterest的
上一篇文章
下一篇

关于作者

前开发者教程

每天我们都会讨论竞争性编程问题,请加入我们的网站:   电报频道

ProDeveloperTutorial.com

教程和编程解决方案
版权© 2020 ProDeveloperTutorial.com
从以下课程获得热门课程: 教育性的




  • <tfoot id="DVDmKrW"><blockquote id="CcMm3fc"></blockquote></tfoot>