欢迎大家来到IT世界,在知识的湖畔探索吧!

产生背景

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

核心思想

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

动态规划在算法中的概念及运用

动态规划遵循一套固定的流程：递归的暴力解法( O(2^n) ) -> 带备忘录的递归解法( O(n) ) -> 非递归的动态规划解法( O(n) )。

「自顶向下」： 是从上向下延伸， 都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 触底，然后逐层返回答案。

「自底向上」： 直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，

还有三个比较重要的概念：最优子结构，边界，状态转移公式，怎么理解？请看下面的栗子。

简单示例

举个例子，斐波那契数列 0,1,1,2,3,5,8,13,…有着一个相当简单的描述方式，它的每个数字都与前两个紧邻的数字相关。如果 F(n) 是第 n 个数字，那么我们会有 F(n) = F(n-1) + F(n-2)。这个在数学上称作*递归方程*或者*递推关系*。为了计算后面的项，它需要前面项的计算结果作为输入。

此时，假设n=10,F(9),F(8)就是最优子结构，F(0)和F(1)就是边界，没有边界结没办法得到有限的结果,自然状态转移公式就是F(n) = F(n-1) + F(n-2)。

递归+备忘录java代码示例：

程序运行结果：

非递归动态规划代码示例：

运行结果：

由上面的例子可知，两个例子都是从边界值自底向上的算法，时间复杂度都为O(n)，空间复杂度O(n).

关于动态规划分析流程

由上例，可得出如下步骤：

1. 将原问题分解为子问题 f(0),f(1),f(2)…f(n)

2. 确定状态 f(n)

3. 确定一些初始状态(边界条件)的值 f(n)=0

4. 确定状态转移方程（当前子问题值与前一个子问题值的关系） f(n) 是一个状态 n，这个状态 n 是由状态 n – 1 和状态 n – 2 相加转移而来，这就是状态转移 动态规划问题最困难的就是写出状态转移方程。

适用场景

1. 问题具有最优子结构（问题的最优解所包含的子问题的解也是最优的）

2. 求最优解问题

几个经典的面试题

1.爬楼梯，求共多少爬法（n为正整数）

1.1，递归（时间复杂度近似O(2^N)）

1.2，备忘录(时间复杂度O(n))

1.3,动态规划（时间复杂度O(n),空间复杂度O(1)）

2.打家劫舍：求可以盗取的最大数（不能盗取相邻元素）

3.给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

4.最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1

5.三角形最小路径和（给定一个三角形，找出最小路径和。每一步只能移动到下一行中相邻的结点上）

6.给定一个无序的整数数组，找到其中最长上升子序列的长度

7.给定一个包含非负整数的网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小（只能向下或者向右移动一步）

8.国王和金矿

有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

动态规划解法：

案例部分来自于网络，可能存在比他们更优的解法，欢迎拍砖。

小编喜欢和你们共同进步，走上人生巅峰，喜欢就关注一下吧，谢谢~~