项目中要使用到动态规划该怎么应用，怎么说？

野性酷女 2023-07-18 03:11 21阅读 0赞

因为前一段接了个项目，所以呢，其实在前一段时间我就有写过关于动态规划的一篇文章——浅谈一下这个所谓的特殊算法——动态规划！链接如下：

> [https://blog.csdn.net/qq\_41946557/article/details/104704964][https_blog.csdn.net_qq_41946557_article_details_104704964]

但是在项目的讲述中，如果我要使用到它，我怎么讲述？忽的这样一想，好像对其算法好像并没有自己想的那个随意。所以再来说到说到这个动态规划！

我们在一些搜索引擎上搜索——基于动态规划时，你会发现关于使用动态规划的领域，可谓是各行各业。比如：基于动态规划的资源分配问题，基于动态规划的路径规划方法等等等。其实早在最初的浅谈动态规划中，我就提出过DP实际意义上说是一个方法，并非一个算法！！

下面我先主要针对于动态编程进行一定的解释说明：

![format_png][]

**维基百科**的意思大致是：*动态编程既是数学优化方法又是计算机编程方法。该方法是由理查德·贝尔曼（Richard Bellman）在1950年代开发的，并且已在从航空工程到经济学的许多领域中得到应用。在这两种情况下，它都是指通过以递归方式将其分解为更简单的子问题来简化一个复杂的问题。尽管无法以这种方式解决某些决策问题，但是跨越多个时间点的决策通常会递归拆分。同样，在计算机科学中，如果可以通过将问题分解为子问题然后递归地找到子问题的最优解来最佳地解决问题，则可以说它具有最优子结构。*

## 动态编程的介绍 ##

动态编程是解决优化问题的最强大的设计技术。

分而治之算法将问题划分为不相交的子问题，然后递归地解决子问题，然后结合其解决方案来解决原始问题。

当子问题不是独立的时，例如当它们共享相同的子问题时，使用动态编程。在这种情况下，分治法可能会做比必要的更多的工作，因为它可以多次解决同一个子问题。

动态编程仅解决每个子问题一次，并将结果存储在表中，以便在需要时可以重复检索它。

动态编程是一种\*\*自下而上的方法-\*\*我们解决所有可能的小问题，然后结合以获得更大问题的解决方案。

动态规划是一种算法设计的范式，其中，通过实现子问题解决方案以及出现“ **最优原理** ” 的组合来解决优化问题。

## 动态编程的特点 ##

当问题具有以下特征时，动态编程将起作用：

*  \*\*最优子结构：\*\*如果最优解决方案包含最优子解决方案，那么问题将表现出最优子结构。
 *  \*\*子问题重叠：\*\*当递归算法将重复访问相同的子问题时，则问题将具有子问题重叠。

如果问题具有最佳子结构，则可以递归定义最佳解决方案。如果问题有重叠的子问题，那么我们可以通过仅计算每个子问题一次来改进递归实现。

如果问题没有最佳子结构，则没有基础来定义递归算法以找到最佳解决方案。如果一个问题没有重叠的子问题，那么使用动态编程就无济于事。

如果子问题的空间足够大（即输入大小为多项式），则动态编程比递归更有效。

![format_png 1][]

## 动态编程的要素 ##

基本上，三个要素是动态编程算法的特征：

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SWAX3nC3-1584971186276)(https://static.javatpoint.com/tutorial/daa/images/elements-of-dynamic-programming.png)\]

1.  \*\*子结构：\*\*将给定问题分解为较小的子问题。用较小问题的解决方案来表达原始问题的解决方案。
2.  \*\*表结构：\*\*解决了子问题后，将结果存储到表中的子问题中。这样做是因为子问题解决方案已被多次重用，并且我们不想一遍又一遍地重复解决相同的问题。
3.  \*\*自下而上的计算：\*\*使用表格，将较小的子问题的解决方案组合起来以解决较大的子问题，并最终得出解决问题的解决方案。

**注意：自下而上是指：-**

1.  从最小的子问题开始。
2.  结合他们的解决方案，可以解决规模越来越大的子问题。
3.  直到解决原始问题为止。

## 动态编程的组成部分 ##

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Lzi92vLo-1584971186276)(https://static.javatpoint.com/tutorial/daa/images/components-of-dynamic-programming.png)\]

1.  \*\*阶段：\*\*问题可以分为几个子问题，称为子阶段。阶段是给定问题的一小部分。例如，在最短路径问题中，它们是由图的结构定义的。
2.  状态\*\*：\*\*每个阶段都有几个与之相关的状态。最短路径问题的状态是到达的节点。
3.  \*\*决策：\*\*在每个阶段，可以有多个选择，应从中做出最好的决定之一。在每个阶段做出的决定都应该是最佳的；这称为阶段决策。
4.  \*\*最优政策：\*\*这是一个决定每个阶段决策的规则；如果策略是全局最优的，则称为最优策略。这就是最佳贝尔曼原理。
5.  给定当前状态，其余每个状态的最佳选择均不取决于先前的状态或决策。在最短路径问题中，没有必要仅知道我们如何获得节点。
6.  鉴于已经解决了阶段j + 1，存在一种递归关系，该关系确定阶段j的最佳决策。
7.  最后阶段必须自己解决。

## 动态规划算法的发展 ##

它可以分为四个步骤：

1.  表征最佳解决方案的结构。
2.  递归定义最佳解决方案的值。像“分而治之”一样，将问题递归分为两个或多个最佳部分。这有助于确定解决方案的外观。
3.  从下至上计算最佳解决方案的值（从最小的子问题开始）
4.  从较小的子问题的计算值构造整个问题的最佳解决方案。

## 动态编程的应用 ##

1.  0/1背包问题
2.  数学优化问题
3.  所有对最短路径问题
4.  可靠性设计问题
5.  最长公共子序列（LCS）
6.  飞行控制和机器人控制
7.  分时：它计划作业以最大化CPU使用率

## 简单举一个动态编程的例子 ##

太少写算法的东西，所以这里以斐波那契做一个例子。后面举几个其他的例子，自行演示吧

斐波那契数是以下整数序列中的数字。

0，1，1，2，3，5，8，13，21，34，55，89，144，…

用数学术语来说，斐波纳契数的序列Fn由递归关系定义

F n = F n-1 + F n-2

具有种子值

F 0 = 0和F 1 = 1。

给定数字n，打印第n个斐波那契数。  
**例子：**

输入：n = 2
    输出1
    
    输入：n = 9
    输出：34

### 方法1（使用递归） ###

一种简单的方法，它是上面给出的直接递归实现数学递归关系。

//Fibonacci Series using Recursion 
    class fibonacci 
    {  
    	static int fib(int n) 
    	{  
    	if (n <= 1) 
    	return n; 
    	return fib(n-1) + fib(n-2); 
    	} 
    	
    	public static void main (String args[]) 
    	{  
    	int n = 9; 
    	System.out.println(fib(n)); 
    	} 
    } 
    /* This code is contributed by Rajat Mishra */

输出量

*时间复杂度：* T（n）= T（n-1）+ T（n-2）是指数的。  
我们可以观察到该实现做了很多重复的工作（请参见下面的递归树）。因此，对于第n个斐波那契数，这是一个错误的实现。

fib（5）    
                         / \ 
                   fib（4）fib（3）    
                 / \ / \ 
             fib（3）fib（2）fib（2）fib（1）
            / \ / \ / \ 
      fib（2）fib（1）fib（ 1）fib（0）fib（1）fib（0）
      / \ 
    fib（1）fib（0）

\*额外空间：\*如果考虑函数调用堆栈的大小，则为O（n），否则为O（1）。

**方法2（使用动态编程）**  
通过存储到目前为止计算出的斐波那契数，我们可以避免方法1的重复工作。

// Fibonacci Series using Dynamic Programming 
    class fibonacci 
    {  
    static int fib(int n) 
    	{  
    	/* Declare an array to store Fibonacci numbers. */
    	int f[] = new int[n+2]; // 1 extra to handle case, n = 0 
    	int i; 
    	
    	/* 0th and 1st number of the series are 0 and 1*/
    	f[0] = 0; 
    	f[1] = 1; 
    	
    	for (i = 2; i <= n; i++) 
    	{  
    	/* Add the previous 2 numbers in the series and store it */
    		f[i] = f[i-1] + f[i-2]; 
    	} 
    	
    	return f[n]; 
    	} 
    	
    	public static void main (String args[]) 
    	{  
    		int n = 9; 
    		System.out.println(fib(n)); 
    	} 
    } 
    /* This code is contributed by Rajat Mishra */

当然这只是使用动态规划进行的优化，具体优化还有比如优化空间、使用矩阵等方式。

其他高深的关于动态规划的算法自行百度吧。或者关注一下，等我下次有空专门来一篇。哈哈

其实根据上述的例子，你或许就有了一些想法和思路，没错在整体的数据分析中，比如最近开展的智慧交通，我们难免在大量的数据中分析各种TopN，那么每次的查询我们都要进行重新的在大量的数据中进行去取TopN吗？我们能不能使用一个动态规划对程序进行优化，对每次的TopN进行存储，避免每次的重复工作。当然不仅仅限于TopN的问题。在编程和计算中均可以进行应用，这也是目前我觉得最简单的引用DP的方式。至于其他的后续再聊了。

我有一壶酒，足以慰风尘。感觉对你有点帮助的话，给个关注呗！或者点个赞再走喽！

参考资料：https://www.javatpoint.com/dynamic-programming-introduction

[https_blog.csdn.net_qq_41946557_article_details_104704964]: https://blog.csdn.net/qq_41946557/article/details/104704964
[format_png]: /images/20230528/22e38c005e004ebf865bcbe577b62c0c.png
[format_png 1]: /images/20230528/dc175a76382440729280e4a52d082f23.png