动态规划 订阅
动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果 [1]  。 展开全文
动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果 [1]  。
信息
运    用
求解决策过程(decision process)最优化的数学方法
外文名
dynamic programming
简    称
DP
中文名
动态规划
学    科
运筹学
第一本著作
《Dynamic Programming》
动态规划简介
动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便 [2]  。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解 [2]  。在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定,它依赖于当前面临的状态,又影响以后的发展。当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线.这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题称为多阶段决策问题。在多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化的过程为动态规划方法 [3]  。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式 [4]  。1. 多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段,在每一个阶段都需作出决策(采取措施),一个阶段的决策确定以后,常常影响到下一个阶段的决策,从而就完全确定了一个过程的活动路线,则称它为多阶段决策问题 [5]  。各个阶段的决策构成一个决策序列,称为一个策略。每一个阶段都有若干个决策可供选择,因而就有许多策略供我们选取,对应于一个策略可以确定活动的效果,这个效果可以用数量来确定。策略不同,效果也不同,多阶段决策问题,就是要在可以选择的那些策略中间,选取一个最优策略,使在预定的标准下达到最好的效果 [5]  。2.动态规划问题中的术语阶段:把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,阶段数就可能不同.描述阶段的变量称为阶段变量。在多数情况下,阶段变量是离散的,用k表示。此外,也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策,且在任意两个不同的时刻之间允许有无穷多个决策时,阶段变量就是连续的 [5]  。状态:状态表示每个阶段开始面临的自然状况或客观条件,它不以人们的主观意志为转移,也称为不可控因素。在上面的例子中状态就是某阶段的出发位置,它既是该阶段某路的起点,同时又是前一阶段某支路的终点 [5]  。无后效性:我们要求状态具有下面的性质:如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。换句话说,过程的每一次实现可以用一个状态序列表示,在前面的例子中每阶段的状态是该线路的始点,确定了这些点的序列,整个线路也就完全确定。从某一阶段以后的线路开始,当这段的始点给定时,不受以前线路(所通过的点)的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性 [5]  。决策:一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择(行动)称为决策。在最优控制中,也称为控制。在许多问题中,决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量,因状态满足无后效性,故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史 [5]  。决策变量的范围称为允许决策集合 [5]  。策略:由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程,可供选取的策略有一定的范围限制,这个范围称为允许策略集合 [5]  。允许策略集合中达到最优效果的策略称为最优策略 [5]  。给定k阶段状态变量x(k)的值后,如果这一阶段的决策变量一经确定,第k+1阶段的状态变量x(k+1)也就完全确定,即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化,那么可以把这一关系看成(x(k),u(k))与x(k+1)确定的对应关系,用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律,称为状态转移方程 [5]  。最优化原理:作为整个过程的最优策略,它满足:相对前面决策所形成的状态而言,余下的子策略必然构成“最优子策略” [5]  。最优性原理实际上是要求问题的最优策略的子策略也是最优 [5]  。多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化问题的方法为动态规划方法 [6]  。任何思想方法都有一定的局限性,超出了特定条件,它就失去了作用。同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性 [7]  。1、最优化原理(最优子结构性质)最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质 [7]  。2、无后效性将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性 [7]  。3、子问题的重叠性动态规划算法的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受,而搜索算法在时间上却无法承受,所以我们舍空间而取时间 [7]  。
收起全文
精华内容
下载资源
问答
  • 动态规划
    千次阅读
    2021-11-04 14:32:30

    今天这篇文章,我们来谈一谈算法中的一种思想————动态规划。

    可能有些读者有接触过动态规划,可能也有一些读者以前完全不知道动态规划这个东西,别担心,我这篇文章会为读者做一个入门,好让读者掌握这个重要的知识点。

    首先,读者需要知道,动态规划实质上是一种思想,并不是以中具体的算法,在面对某些问题的啥时候,我们可以利用动态规划这个思想将问题转化,从而达到解决问题的地步。

    补充一点:动态规划简称dp(全称dynamic programming

    我们通过一下三个问题来了解动态规划。

    问题一:现在有一个n阶的台阶,你一次只能上一步或两步,请问你到第n阶台阶的方法数有多少?这个问题算是动态规划中最简单的问题了,读者可以自己先思考一会,然后在看解析。

    首先,我们来分析一下问题,其实不难发现,我们假设到达第n阶台阶的方法数位dp [n], 那么事实上到达第n阶的方法数就等于到达n - 1阶的方法数加上到达n - 2阶的方法数,所以我们就可以就可以写出关系式 dp[n] = dp[n - 1] + dp[n - 2] 。这个关系式我们把它叫做动态转移方程,可能有眼尖的读者已经可以发现,这不就是数学上的递推式吗?如果你能看出来,那么恭喜你,你很有潜质!

    此题的代码实现如下:

    #include <iostream>
    using namespace std;
    int dp[100] = { 1,1 };
    int main()
    {
    	int n;//n表示台阶数
    	cin >> n;
    	for (int i = 2; i <= n; i++)
    	{
    		dp[n] = dp[n - 1] + dp[n - 2];
    	}
    	cout << dp[n];
    	return 0;
    }

    如果这道题没有运用动态规划的思想,那么正常思考难度极大,但是我们运用动态规划思想,就轻松的将问题迎刃而解了。

    问题二:相信大家已经很熟悉汉诺塔问题了,但是这次的问题是,有n个盘子,求把盘子从A针移到C针的方法数。

    这道题我们这样思考,我们首先需要三个步骤

    1:将n - 1个盘子从A针移到B针(通过C针)

    2:将一个盘子从A针移到C针

    3:将n - 1个盘子从B针移到C针(通过A针)

    我们定义dp[n] 为将n个盘子从一个针移到另外一个针的方法数

    那么原问题就会变成:

    1:将n - 1个盘子从A针移到B针(通过C针)(有dp[n - 1]钟方法)

    2:将一个盘子从A针移到C针 (有一种方法)

    3:将n - 1个盘子从B针移到C针(通过A针) (有dp[n - 1]钟方法)

    通过上述分析,我们就可以写出这道题的动态转移方程:dp[n] = 2 * dp[n - 1] + 1

    所以,我们就可以码出代码,本题代码实现如下:

    #include <iostream>
    using namespace std;
    #define max 100
    int dp[max] = {0,1};
    int main()
    {
    	int n; //n代表有几个碟子
    	cin >> n;
    	for (int i = 2; i <= n; i++)
    	{
    		dp[i] = 2 * dp[i - 1] + 1;
    	}
    	cout << dp[n];
    	return 0;
    }

    这题也是一样,正常去思考难度极大,但是通过动态规划,我们也是将问题迎刃而解了。

    相信看到这里,读者已经对动态规划有了一定的了解,接下来这题将是本文的最后一道例题,同时也是最难的一道。

    题目:现在假设:你有足够的长度分别为1,2,3,……,n的长条积木,你有多少种搭出高度为h的上升三角塔(每个积木横着放,高度都为1)”
    解释:积木横着搭高,上面的积木长度不得大于下面的积木,例如高度为4,从上往下积木的长度分别为1223和1234为上升三角塔,但1232不是上升三角塔。

    输入要求:只有一行包括两个正整数n, h(0< n < 40, 0 < h < 40),n代表长条积木的长度分别为1,2,3,……,n,h代表要搭出的高度
    注意:每个长度(1,2,3,……,n)的积木的数量都是充足的,不用担心不够搭。
    保证答案能用long long存下。

    输出要求:输出一行包括一个正整数,代表方案数

    输入样例:3 3

    输出样例 10

    提示:

    对于第一个样例,10种分别为
    111
    112
    113
    122
    123
    133
    222
    223
    233
    333

    仔细读完题目后,可能读者回想用穷举法来实现,因为我可以一一列举,但事实上,这题是没有办法用列举法实现的,因为高度和长度都是未知的,但是我们编写的程序又是有界的,所以没办法用列举法,但是本题的难点就在于分析出它是一个动态规划问题。

    我们这样去思考,在排列过程中,我们不难发现,第m层长度为k的方法数为第m - 1层从长度为k到n的累加,当h = 1时(高度为1),这时候我们的方法数就是n。

    通过以上分析,我们就可以写出其对应的动态转移方程。

    我们定义,第m层长度为k时的方法数为dp[m][k]。

    此时就会有dp[m][k] = dp[m - 1][ k ] + dp[m - 1][k + 1] + .... + dp[m - 1] [n]

     求完每层长度为k的方法数之后,我们再将其全部累加之后就是我们所要的答案

    代码实现如下:

    #include <iostream>
    using namespace std;
    long long dp[50][50];
    long long sum = 0;
    int main()
    {
    	int n, h;
    	cin >> n >> h;
    	for (int i = 1; i < 49; i++)
    	{
    		dp[1][i] = 1;
    		for (int k = 1; k < 49; k++)
    			dp[i + 1][k] = 0;
    	}
    	for (int m = 2; m <= h; m++)
    	{
    		for (int j = 2; j <= n; j++)
    		{
    			for (int k = j; k <= n; k++)
    			{
    				dp[m][j] += dp[m - 1][k];
    			}
    		}
    	}
    	for (int m = 1; m <= h; m++)
    	{
    		for (int k = 1; k <= n; k++)
    		{
    			sum += dp[m][k];
    		}
    	}
    	cout << sum;
    	return 0;
    }

    好了,以上就是本文的全部内容了。

    回顾一下,本文浅谈动态规划思想,在解决某些问题是堪称神器,但是难点在于如何去分析该问题为一个动态规划问题,本文所写的还不能让读者可以完全掌握动态规划(因为作者也学了没多久换哈哈哈)但主要还是给读者做一个入门,让读者可以先了解一下动态规划是什么,这也是我写这篇文章的初衷,谢谢。

    更多相关内容
  • 贪心算法、分治算法和动态规划的区别 贪心算法和动态规划.pdf
  • 【达摩老生出品,必属...资源名:matlab实现动态规划算法 程序源码.zip 资源类型:程序源代码 源码说明: 基于matlab实现动态规划的程序,包含完整源码和注释,非常适合借鉴学习 适合人群:新手及有一定经验的开发人员
  • 动态规划混合动力汽车模式切换程序,附带工况。
  • Matlab仿真混合动力汽车Simulink模型基于动态规划算(混合动力汽车能量管理)源代码下载 Matlab仿真混合动力汽车Simulink模型基于动态规划算(混合动力汽车能量管理)源代码下载 Matlab仿真混合动力汽车Simulink模型...
  • 完整代码,可直接运行
  • 动态规划计算水库优化调度。本文中使用了下列变重,说明如下:t为时段变重,在本坝目研究中,以旬为计算时段,全年共计36个时段;Vt、Zt为t时段初水库蓄水重及蓄水水位;Qt为t时段平均下泄流量;NtEt为水电站t时段...
  • 动态规划经典试题动态规划经典试题动态规划经典试题动态规划经典试题动态规划经典试题动态规划经典试题动态规划经典试题动态规划经典试题动态规划经典试题动态规划经典试题动态规划经典试题动态规划经典试题动态规划...
  • matlab 动态规划的实现

    2018-04-07 09:57:30
    matlab 动态规划的实现 内含一个背包算法的代码模块,做动态规划的小伙伴们可以参考一下,背包算法可以单独使用,在matlab下运行第一个文件即可
  • 会议安排(贪心算法和动态规划) 贪心算法和动态规划.pdf
  • 动态规划是信息学竞赛中的常见算法,本文的主要内容就是分析 它的特点。 文章的第一部分首先探究了动态规划的本质,因为动态规划的特 点是由它的本质所决定的。第二部分从动态规划的设计和实现这两个 角度分析了动态...
  • 动态规划算法——C++实现经典案例——初级
  • 动态规划算法ppt

    2019-01-10 13:44:11
    动态规划算法ppt讲义
  • 通过动态规划的思想解决电路布线问题。 主要分为两个部分:1.求size[i][j]. 2.根据求得的size[i][j]导出最大不相交连线集。
  • 动态规划混合动力汽车能量管理matlab程序(包括速度mat)
  • 动态规划模型的讲解,例题及相应算法解答。
  • 动态规划写的灰度压缩解压,只适合bmp文件,包含压缩和解压
  • 关于线性规划、整数规划、非线性规划、动态规划、图与网络
  • 动态规划

    千次阅读 2020-08-07 21:05:35
    1. 什么是动态规划 从数学的视角来看,动态规划是一种运筹学方法,是在多轮决策过程中的最优方法。 那么,什么是多轮决策呢?其实多轮决策的每一轮都可以看作是一个子问题。从分治法的视角来看,每个子问题必须相互...

    1. 什么是动态规划

    从数学的视角来看,动态规划是一种运筹学方法,是在多轮决策过程中的最优方法。

    那么,什么是多轮决策呢?其实多轮决策的每一轮都可以看作是一个子问题。从分治法的视角来看,每个子问题必须相互独立。但在多轮决策中,这个假设显然不成立。这也是动态规划方法产生的原因之一

    2. 最短路径问题

    接下来看一个非常典型的例子,最短路径问题。如下图所示:
    在这里插入图片描述
    每个结点是一个位置,每条边是两个位置之间的距离。现在需要求解出一条由 A 到 G 的最短距离是多少。

    不难发现,我们需要求解的路线是由 A 到 G,这就意味着 A 要先到 B,再到 C,再到 D,再到 E,再到 F。每一轮都需要做不同的决策,而每次的决策又依赖上一轮决策的结果。

    例如,做 D2 -> E 的决策时,D2 -> E2 的距离为 1,最短。但这轮的决策,基于的假设是从 D2 出发,这就意味着前面一轮的决策结果是 D2。由此可见,相邻两轮的决策结果并不是独立的

    动态规划还有一个重要概念叫作状态。在这个例子中,状态是个变量,而且受决策动作的影响。例如,第一轮决策的状态是 S1,可选的值是 A,第二轮决策的状态是 S2,可选的值就是 B1 和 B2。以此类推。

    3. 动态规划的基本方法

    动态规划问题之所以难,是因为动态规划的解题方法并没有那么标准化,它需要你因题而异,仔细分析问题并寻找解决方案。虽然动态规划问题没有标准化的解题方法,但它有一些宏观层面通用的方法论

    下面的 k 表示多轮决策的第 k 轮

    1. 分阶段,将原问题划分成几个子问题。一个子问题就是多轮决策的一个阶段,它们可以是不满足独立性的。
    2. 找状态,选择合适的状态变量 Sk。它需要具备描述多轮决策过程的演变,更像是决策可能的结果。
    3. 做决策,确定决策变量 uk。每一轮的决策就是每一轮可能的决策动作,例如 D2 的可能的决策动作是 D2 -> E2 和 D2 ->E3。
    4. 状态转移方程。这个步骤是动态规划最重要的核心,即 sk+1= uk(sk) 。
    5. 定目标。写出代表多轮决策目标的指标函数 Vk,n。
    6. 寻找终止条件。

    了解了方法论、状态、多轮决策之后,我们再补充一些动态规划的基本概念。

    • 策略,每轮的动作是决策,多轮决策合在一起常常被称为策略。
    • 策略集合,由于每轮的决策动作都是一个变量,这就导致合在一起的策略也是一个变量。我们通常会称所有可能的策略为策略集合。因此,动态规划的目标,也可以说是从策略集合中,找到最优的那个策略。

    一般而言,具有如下几个特征的问题,可以采用动态规划求解:

    1. 最优子结构。它的含义是,原问题的最优解所包括的子问题的解也是最优的。例如,某个策略使得 A 到 G 是最优的。假设它途径了Fi,那么它从 A 到 Fi 也一定是最优的。
    2. 无后效性。某阶段的决策,无法影响先前的状态。可以理解为今天的动作改变不了历史。
    3. 有重叠子问题。也就是,子问题之间不独立。这个性质是动态规划区别于分治法的条件。如果原问题不满足这个特征,也是可以用动态规划求解的,无非就是杀鸡用了宰牛刀。

    4. 案例

    到这里,动态规划的概念和方法就讲完了。接下来,我们以最短路径问题再来看看动态规划的求解方法。在这个问题中,你可以采用最暴力的方法,那就是把所有的可能路径都遍历一遍,去看哪个结果的路径最短的。如果采用动态规划方法,那么我们按照方法论来执行。

    4.1 动态规划的求解方法
    具体的解题步骤如下:

    • 分阶段 很显然,从 A 到 G,可以拆分为 A -> B、B -> C、C -> D、D -> E、E -> F、F -> G,6
      个阶段。

    • 找状态
      第一轮的状态 S1 = A,第二轮 S2 = {B1,B2},第三轮 S3 = {C1,C2,C3,C4},第四轮 S4 = {D1,D2,D3},第五轮 S5 = {E1,E2,E3},第六轮 S6 = {F1,F2},第七轮 S7 = {G}。

    • 做决策
      决策变量就是上面图中的每条边。我们以第四轮决策 D -> E 为例来看,可以得到 u4(D1),u4(D2),u4(D3)。其中 u4(D1) 的可能结果是 E1 和 E2。

    • 写出状态转移方程
      在这里,就是 sk+1 = uk(sk)。

    • 定目标
      别忘了,我们的目标是总距离最短。我们定义 dk(sk,uk) 是在 sk 时,选择 uk 动作的距离。例如,d5(E1,F1) = 3。那么此时 n = 7,则有,
      v k , 7 ( s 1 = A , s 7 = G ) = ∑ k = 1 7 d k ( s k , u k ) v_{k, 7}\left(s_{1}=A, s_{7}=G\right)=\sum_{k=1}^{7} d_{k}\left(s_{k}, u_{k}\right) vk,7(s1=A,s7=G)=k=17dk(sk,uk)
      就是最终要优化的目标。

    • 寻找终止条件

    • 很显然,这里的起止条件分别是,s1 = A 和 s7 = G。

    • 接下来,我们把所有的已知条件,凝练为上面的符号之后,只需要借助最优子结构,就可以把问题解决了。最优子结构的含义是,原问题的最优解所包括的子问题的解也是最优的。

    • 套用在这个例子的含义就是,如果 A -> … -> F1 -> G 是全局 A 到 G 最优的路径,那么此处 A -> … ->
      F1 也是 A 到 F1 的最优路径。

    • 因此,此时的优化目标 min Vk,7(s1=A, s7=G),等价于 min { Vk,6(s1=A, s6=F1)+4,
      Vk,6(s1=A, s6=F2)+3 }。

    • 此时,优化目标的含义为,从 A 到 G 的最短路径,是 A 到 F1 到 G 的路径和 A 到 F2 到 G 的路径中更短的那个。

    • 同样的,对于上面式子中,Vk,6(s1=A,s6=F1) 和 Vk,6(s1=A,s6=F2),仍然可以递归地使用上面的分析方法。

    4.2 计算过程详解
    好了,为了让大家清晰地看到结果,我们给出详细的计算过程。为了书写简单,我们把函数 Vk,7(s1=A, s7=G) 精简为 V7(G),含义为经过了 6 轮决策后,状态到达 G 后所使用的距离。我们把图片复制到这里一份,方便大家不用上下切换。
    在这里插入图片描述
    我们的优化目标为 min Vk,7(s1=A, s7=G),因此精简后原问题为,min V7(G)。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    因此,最终输出路径为 A -> B1 -> C2 -> D1 -> E2 -> F2 -> G,最短距离为 18

    4.3 代码实现过程
    接下来,我们尝试用代码来实现上面的计算过程。对于输入的图,可以采用一个 m x m 的二维数组来保存。在这个二维数组里,m 等于全部的结点数,也就是结点与结点的关系图。而数组每个元素的数值,定义为结点到结点需要的距离。
    在这里插入图片描述
    在本例中,可以定义输入矩阵 m(空白处为0),如下图所示:
    在这里插入图片描述

    代码如下:

    public class testpath {
        public static int minPath1(int[][] matrix) {
            return process1(matrix, matrix[0].length-1);
        }
        // 递归
        public static int process1(int[][] matrix, int i) {
            // 到达A退出递归
            if (i == 0) {
                return 0;
            }
            // 状态转移
            else{
                int distance = 999;
                for(int j=0; j<i; j++){
                    if(matrix[j][i]!=0){
                        int d_tmp = matrix[j][i] + process1(matrix, j);
                        if (d_tmp < distance){
                            distance = d_tmp;
                        }
                    }
                }
                return distance;
            }
        }
        public static void main(String[] args) {
            int[][] m = {{0,5,3,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,1,3,6,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,8,7,6,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,6,8,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,3,5,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,3,3,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,8,4,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,2,2,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,1,2,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,3,3,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,3,5,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,5,2,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,6,6,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3}};
            System.out.println(minPath1(m));
        }
    }
    

    代码解读:

    代码的 27 行是主函数,在代码中定义了二维数组 m,对应于输入的距离图。m 是 15 x 16 维的,我们忽略了最后一行的全 0(即使输入也不会影响结果)。

    然后调用函数 minPath1。在第 2 到第 4 行,它的内部又调用了 process1(matrix, matrix[0].length-1)。在这里,matrix[0].length-1 的值是 15,表示的含义是 matrix 数组的第 16 列(G)是目的地。

    接着进入 process1 函数中。我们知道在动态规划的过程中,是从后往前不断地推进结果,这就是状态转移的过程。对应代码中的 13-24 行

    • 第 15 行开始循环,j 变量是纵向的循环变量。
    • 第 16 行判断 matrix[j][i] 与 0 的关系,含义为,只有值不为 0 才说明两个结点之间存在通路。
    • 一旦发现某个通路,就需要计算其距离。计算的方式是 17 行的
      d_tmp = matrix[j][i] + process1(matrix, j)
    • 当得到了距离之后,还需要找到最短的那个距离,也就是 18 到 20 行的含义。这就是动态规划最优子结构的体现。
    • 一旦 i 减小到了 0,就说明已经到了起点 A。那么 A 到 A 的距离就是 0,直接第 10 行的 return 0 就可以了。
    • 经过运行,这段代码的输出结果是 18,这与我们手动的推导结果一致。
      本文参考拉钩教育学习视频
    展开全文
  • 动态规划VB程序

    2016-02-24 16:13:24
    利用VB代码编写动态规划的程序,水库优化调度的具体示例
  • 自适应动态规划matalab简单代码实现,适合初学者,代码可运行
  • 关于动态规划投资问题的Java代码实现,帮助了解具体算法的实现过程
  • 代码 基于动态规划离散优化问题代码代码 基于动态规划离散优化问题代码代码 基于动态规划离散优化问题代码代码 基于动态规划离散优化问题代码代码 基于动态规划离散优化问题代码代码 基于动态规划离散优化问题代码...
  • 动态规划的基本思想和基本步骤,通过实例研究了利用动态规划设计算法的具体途径,讨论了动态规划的一些实现技巧,并将动态规划和其他一些算法作了比较
  • 代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的matlab代码代码 随机动态规划的实例的...
  • 动态规划是求解最优化问题的一种方法;动态规划虽然空间复杂度一般较大,但时间效率可观。但是,动态规划在求解中也会存在一些不必要、或者重复求解的子问题,这时就需要进行进一步优化。 在NOI及省选赛场上,一般...
  • 动态规划难吗?说实话,我觉得很难,特别是对于初学者来说,我当时入门动态规划的时候,是看 0-1 背包问题,当时真的是一脸懵逼。后来,我遇到动态规划的题,看的懂答案,但就是自己不会做,不知道怎么下手。就像做...

    动态规划难吗?说实话,我觉得很难,特别是对于初学者来说,我当时入门动态规划的时候,是看 0-1 背包问题,当时真的是一脸懵逼。后来,我遇到动态规划的题,看的懂答案,但就是自己不会做,不知道怎么下手。就像做递归的题,看的懂答案,但下不了手,关于递归的,我之前也写过一篇套路的文章,如果对递归不大懂的,强烈建议看一看:为什么你学不会递归,告别递归,谈谈我的经验

    对于动态规划,春招秋招时好多题都会用到动态规划,一气之下,再 leetcode 连续刷了几十道题

    在这里插入图片描述

    之后,豁然开朗 ,感觉动态规划也不是很难,今天,我就来跟大家讲一讲,我是怎么做动态规划的题的,以及从中学到的一些套路。相信你看完一定有所收获

    如果你对动态规划感兴趣,或者你看的懂动态规划,但却不知道怎么下手,那么我建议你好好看以下,这篇文章的写法,和之前那篇讲递归的写法,是差不多一样的,将会举大量的例子。如果一次性看不完,建议收藏,同时别忘了素质三连

    为了兼顾初学者,我会从最简单的题讲起,后面会越来越难,最后面还会讲解,该如何优化。因为 80% 的动规都是可以进行优化的。不过我得说,如果你连动态规划是什么都没听过,可能这篇文章你也会压力山大。

    一、动态规划的三大步骤

    动态规划,无非就是利用历史记录,来避免我们的重复计算。而这些历史记录,我们得需要一些变量来保存,一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤,

    如果你听不懂,也没关系,下面会有很多例题讲解,估计你就懂了。之所以不配合例题来讲这些步骤,也是为了怕你们脑袋乱了

    第一步骤:定义数组元素的含义,上面说了,我们会用一个数组,来保存历史数组,假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点,就是规定你这个数组元素的含义,例如你的 dp[i] 是代表什么意思?

    第二步骤:找出数组元素之间的关系式,我觉得动态规划,还是有一点类似于我们高中学习时的归纳法的,当我们要计算 dp[n] 时,是可以利用 dp[n-1],dp[n-2]…dp[1],来推出 dp[n] 的,也就是可以利用历史数据来推出新的元素值,所以我们要找出数组元素之间的关系式,例如 dp[n] = dp[n-1] + dp[n-2],这个就是他们的关系式了。而这一步,也是最难的一步,后面我会讲几种类型的题来说。

    学过动态规划的可能都经常听到最优子结构,把大的问题拆分成小的问题,说时候,最开始的时候,我是对最优子结构一梦懵逼的。估计你们也听多了,所以这一次,我将换一种形式来讲,不再是各种子问题,各种最优子结构。所以大佬可别喷我再乱讲,因为我说了,这是我自己平时做题的套路。

    第三步骤:找出初始值。学过数学归纳法的都知道,虽然我们知道了数组元素之间的关系式,例如 dp[n] = dp[n-1] + dp[n-2],我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n],但是,我们得知道初始值啊,例如一直推下去的话,会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了,所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值,而这,就是所谓的初始值

    由了初始值,并且有了数组元素之间的关系式,那么我们就可以得到 dp[n] 的值了,而 dp[n] 的含义是由你来定义的,你想求什么,就定义它是什么,这样,这道题也就解出来了。

    不懂?没事,我们来看三四道例题,我讲严格按这个步骤来给大家讲解。

    二、案例详解

    案例一、简单的一维 DP

    问题描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

    (1)、定义数组元素的含义

    按我上面的步骤说的,首先我们来定义 dp[i] 的含义,我们的问题是要求青蛙跳上 n 级的台阶总共由多少种跳法,那我们就定义 dp[i] 的含义为:跳上一个 i 级的台阶总共有 dp[i] 种跳法。这样,如果我们能够算出 dp[n],不就是我们要求的答案吗?所以第一步定义完成。

    (2)、找出数组元素间的关系式

    我们的目的是要求 dp[n],动态规划的题,如你们经常听说的那样,就是把一个规模比较大的问题分成几个规模比较小的问题,然后由小的问题推导出大的问题。也就是说,dp[n] 的规模为 n,比它规模小的是 n-1, n-2, n-3… 也就是说,dp[n] 一定会和 dp[n-1], dp[n-2]…存在某种关系的。我们要找出他们的关系。

    那么问题来了,怎么找?

    这个怎么找,是最核心最难的一个,我们必须回到问题本身来了,来寻找他们的关系式,dp[n] 究竟会等于什么呢?

    对于这道题,由于情况可以选择跳一级,也可以选择跳两级,所以青蛙到达第 n 级的台阶有两种方式

    一种是从第 n-1 级跳上来

    一种是从第 n-2 级跳上来

    由于我们是要算所有可能的跳法的,所以有 dp[n] = dp[n-1] + dp[n-2]。

    (3)、找出初始条件

    当 n = 1 时,dp[1] = dp[0] + dp[-1],而我们是数组是不允许下标为负数的,所以对于 dp[1],我们必须要直接给出它的数值,相当于初始值,显然,dp[1] = 1。一样,dp[0] = 0.(因为 0 个台阶,那肯定是 0 种跳法了)。于是得出初始值:

    dp[0] = 0.
    dp[1] = 1.
    即 n <= 1 时,dp[n] = n.

    三个步骤都做出来了,那么我们就来写代码吧,代码会详细注释滴。

    int f( int n ){
    	if(n <= 1)
    	return n;
    	// 先创建一个数组来保存历史数据
    	int[] dp = new int[n+1];
    	// 给出初始值
    	dp[0] = 0;
    	dp[1] = 1;
    	// 通过关系式来计算出 dp[n]
    	for(int i = 2; i <= n; i++){
    		dp[i] = dp[i-1] + dp[-2];
    	}
    	// 把最终结果返回
    	return dp[n];
    }
    
    (4)、再说初始化

    大家先想以下,你觉得,上面的代码有没有问题?

    答是有问题的,还是错的,错在对初始值的寻找不够严谨,这也是我故意这样弄的,意在告诉你们,关于初始值的严谨性。例如对于上面的题,当 n = 2 时,dp[2] = dp[1] + dp[0] = 1。这显然是错误的,你可以模拟一下,应该是 dp[2] = 2。

    也就是说,在寻找初始值的时候,一定要注意不要找漏了,dp[2] 也算是一个初始值,不能通过公式计算得出。有人可能会说,我想不到怎么办?这个很好办,多做几道题就可以了。

    下面我再列举三道不同的例题,并且,再在未来的文章中,我也会持续按照这个步骤,给大家找几道有难度且类型不同的题。下面这几道例题,不会讲的特性详细哈。实际上 ,上面的一维数组是可以把空间优化成更小的,不过我们现在先不讲优化的事,下面的题也是,不讲优化版本。

    案例二:二维数组的 DP

    我做了几十道 DP 的算法题,可以说,80% 的题,都是要用二维数组的,所以下面的题主要以二维数组为主,当然有人可能会说,要用一维还是二维,我怎么知道?这个问题不大,接着往下看。

    问题描述

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

    机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

    问总共有多少条不同的路径?

    在这里插入图片描述

    这是 leetcode 的 62 号题:https://leetcode-cn.com/problems/unique-paths/

    还是老样子,三个步骤来解决。

    步骤一、定义数组元素的含义

    由于我们的目的是从左上角到右下角一共有多少种路径,那我们就定义 dp[i] [j]的含义为:当机器人从左上角走到(i, j) 这个位置时,一共有 dp[i] [j] 种路径。那么,dp[m-1] [n-1] 就是我们要的答案了。

    注意,这个网格相当于一个二维数组,数组是从下标为 0 开始算起的,所以 右下角的位置是 (m-1, n - 1),所以 dp[m-1] [n-1] 就是我们要找的答案。

    步骤二:找出关系数组元素间的关系式

    想象以下,机器人要怎么样才能到达 (i, j) 这个位置?由于机器人可以向下走或者向右走,所以有两种方式到达

    一种是从 (i-1, j) 这个位置走一步到达

    一种是从(i, j - 1) 这个位置走一步到达

    因为是计算所有可能的步骤,所以是把所有可能走的路径都加起来,所以关系式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。

    步骤三、找出初始值

    显然,当 dp[i] [j] 中,如果 i 或者 j 有一个为 0,那么还能使用关系式吗?答是不能的,因为这个时候把 i - 1 或者 j - 1,就变成负数了,数组就会出问题了,所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的,相当于计算机图中的最上面一行和左边一列。因此初始值如下:

    dp[0] [0….n-1] = 1; // 相当于最上面一行,机器人只能一直往左走

    dp[0…m-1] [0] = 1; // 相当于最左面一列,机器人只能一直往下走

    撸代码

    三个步骤都写出来了,直接看代码

    public static int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
    
        int[][] dp = new int[m][n]; // 
      	// 初始化
      	for(int i = 0; i < m; i++){
          dp[i][0] = 1;
        }
      	for(int i = 0; i < n; i++){
          dp[0][i] = 1;
        }
    		// 推导出 dp[m-1][n-1]
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
    

    O(n*m) 的空间复杂度可以优化成 O(min(n, m)) 的空间复杂度的,不过这里先不讲

    案例三、二维数组 DP

    写到这里,有点累了,,但还是得写下去,所以看的小伙伴,你们可得继续看呀。下面这道题也不难,比上面的难一丢丢,不过也是非常类似

    问题描述

    给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

    **说明:**每次只能向下或者向右移动一步。

    举例:
    输入:
    arr = [
      [1,3,1],
      [1,5,1],
      [4,2,1]
    ]
    输出: 7
    解释: 因为路径 1→3→1→1→1 的总和最小。
    

    和上面的差不多,不过是算最优路径和,这是 leetcode 的第64题:https://leetcode-cn.com/problems/minimum-path-sum/

    还是老样子,可能有些人都看烦了,哈哈,但我还是要按照步骤来写,让那些不大懂的加深理解。有人可能觉得,这些题太简单了吧,别慌,小白先入门,这些属于 medium 级别的,后面在给几道 hard 级别的。

    步骤一、定义数组元素的含义

    由于我们的目的是从左上角到右下角,最小路径和是多少,那我们就定义 dp[i] [j]的含义为:当机器人从左上角走到(i, j) 这个位置时,最下的路径和是 dp[i] [j]。那么,dp[m-1] [n-1] 就是我们要的答案了。

    注意,这个网格相当于一个二维数组,数组是从下标为 0 开始算起的,所以 由下角的位置是 (m-1, n - 1),所以 dp[m-1] [n-1] 就是我们要走的答案。

    步骤二:找出关系数组元素间的关系式

    想象以下,机器人要怎么样才能到达 (i, j) 这个位置?由于机器人可以向下走或者向右走,所以有两种方式到达

    一种是从 (i-1, j) 这个位置走一步到达

    一种是从(i, j - 1) 这个位置走一步到达

    不过这次不是计算所有可能路径,而是计算哪一个路径和是最小的,那么我们要从这两种方式中,选择一种,使得dp[i] [j] 的值是最小的,显然有

    dp[i] [j] = min(dp[i-1][j],dp[i][j-1]) + arr[i][j];// arr[i][j] 表示网格种的值
    
    步骤三、找出初始值

    显然,当 dp[i] [j] 中,如果 i 或者 j 有一个为 0,那么还能使用关系式吗?答是不能的,因为这个时候把 i - 1 或者 j - 1,就变成负数了,数组就会出问题了,所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的,相当于计算机图中的最上面一行和左边一列。因此初始值如下:

    dp[0] [j] = arr[0] [j] + dp[0] [j-1]; // 相当于最上面一行,机器人只能一直往左走

    dp[i] [0] = arr[i] [0] + dp[i] [0]; // 相当于最左面一列,机器人只能一直往下走

    代码如下
    public static int uniquePaths(int[][] arr) {
      	int m = arr.length;
      	int n = arr[0].length;
        if (m <= 0 || n <= 0) {
            return 0;
        }
    
        int[][] dp = new int[m][n]; // 
      	// 初始化
      	dp[0][0] = arr[0][0];
      	// 初始化最左边的列
      	for(int i = 1; i < m; i++){
          dp[i][0] = dp[i-1][0] + arr[i][0];
        }
      	// 初始化最上边的行
      	for(int i = 1; i < n; i++){
          dp[0][i] = dp[0][i-1] + arr[0][i];
        }
    		// 推导出 dp[m-1][n-1]
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + arr[i][j];
            }
        }
        return dp[m-1][n-1];
    }
    

    O(n*m) 的空间复杂度可以优化成 O(min(n, m)) 的空间复杂度的,不过这里先不讲

    案例 4:编辑距离

    这次给的这道题比上面的难一些,在 leetcdoe 的定位是 hard 级别。好像是 leetcode 的第 72 号题。

    问题描述

    给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。

    你可以对一个单词进行如下三种操作:

    插入一个字符
    删除一个字符
    替换一个字符

    输入: word1 = "horse", word2 = "ros"
    输出: 3
    解释: 
    horse -> rorse (将 'h' 替换为 'r')
    rorse -> rose (删除 'r')
    rose -> ros (删除 'e')
    

    解答

    还是老样子,按照上面三个步骤来,并且我这里可以告诉你,90% 的字符串问题都可以用动态规划解决,并且90%是采用二维数组。

    步骤一、定义数组元素的含义

    由于我们的目的求将 word1 转换成 word2 所使用的最少操作数 。那我们就定义 dp[i] [j]的含义为:当字符串 word1 的长度为 i,字符串 word2 的长度为 j 时,将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]

    有时候,数组的含义并不容易找,所以还是那句话,我给你们一个套路,剩下的还得看你们去领悟。

    步骤二:找出关系数组元素间的关系式

    接下来我们就要找 dp[i] [j] 元素之间的关系了,比起其他题,这道题相对比较难找一点,但是,不管多难找,大部分情况下,dp[i] [j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某种关系。因为我们的目标就是,从规模小的,通过一些操作,推导出规模大的。对于这道题,我们可以对 word1 进行三种操作

    插入一个字符
    删除一个字符
    替换一个字符

    由于我们是要让操作的次数最小,所以我们要寻找最佳操作。那么有如下关系式:

    一、如果我们 word1[i] 与 word2 [j] 相等,这个时候不需要进行任何操作,显然有 dp[i] [j] = dp[i-1] [j-1]。(别忘了 dp[i] [j] 的含义哈)。

    二、如果我们 word1[i] 与 word2 [j] 不相等,这个时候我们就必须进行调整,而调整的操作有 3 种,我们要选择一种。三种操作对应的关系试如下(注意字符串与字符的区别):

    (1)、如果把字符 word1[i] 替换成与 word2[j] 相等,则有 dp[i] [j] = dp[i-1] [j-1] + 1;

    (2)、如果在字符串 word1末尾插入一个与 word2[j] 相等的字符,则有 dp[i] [j] = dp[i] [j-1] + 1;

    (3)、如果把字符 word1[i] 删除,则有 dp[i] [j] = dp[i-1] [j] + 1;

    那么我们应该选择一种操作,使得 dp[i] [j] 的值最小,显然有

    dp[i] [j] = min(dp[i-1] [j-1],dp[i] [j-1],dp[[i-1] [j]]) + 1;

    于是,我们的关系式就推出来了,

    步骤三、找出初始值

    显然,当 dp[i] [j] 中,如果 i 或者 j 有一个为 0,那么还能使用关系式吗?答是不能的,因为这个时候把 i - 1 或者 j - 1,就变成负数了,数组就会出问题了,所以我们的初始值是计算出所有的 dp[0] [0….n] 和所有的 dp[0….m] [0]。这个还是非常容易计算的,因为当有一个字符串的长度为 0 时,转化为另外一个字符串,那就只能一直进行插入或者删除操作了。

    代码如下
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        // dp[0][0...n2]的初始值
        for (int j = 1; j <= n2; j++) 
        	dp[0][j] = dp[0][j - 1] + 1;
        // dp[0...n1][0] 的初始值
        for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;
    		// 通过公式推出 dp[n1][n2]
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
              	// 如果 word1[i] 与 word2[j] 相等。第 i 个字符对应下标是 i-1
                if (word1.charAt(i - 1) == word2.charAt(j - 1)){
                	p[i][j] = dp[i - 1][j - 1];
                }else {
                   dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
                }         
            }
        }
        return dp[n1][n2];  
    }
    

    最后说下,如果你要练习,可以去 leetcode,选择动态规划专题,然后连续刷几十道,保证你以后再也不怕动态规划了。当然,遇到很难的,咱还是得挂。

    Leetcode 动态规划直达:https://leetcode-cn.com/tag/dynamic-programming/

    三、总结

    上面的这些题,基本都是不怎么难的入门题,除了最后一道相对难一点,本来是要在写几道难一点,并且讲如何优化的,不过看了下字数,文章有点长了,关于如何优化的,后面再讲吧,在之后的文章中,我也会按照这个步骤,在给大家讲四五道动态规划 hard 级别的题,会放在每天推文的第二条给大家学习。如果大家感兴趣,文章看的人多,那么优化篇很快就会撸出来,大家想要第一时间观看我的文章的,可以关注我的个人微信公众号『苦逼的码农』,不过感兴趣的人很少的话,动力比较少,可能就会慢一些,所以各位小伙伴,如果觉得有收获,不放三连走起来,嘻嘻。

    有收获?希望老铁们来个三连击,给更多的人看到这篇文章

    1、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我,嘻嘻。

    2、老铁们,关注我的原创微信公众号「帅地玩编程」,专注于写算法 + 计算机基础知识(计算机网络+ 操作系统+数据库+Linux)。

    保存让你看完有所收获,不信你打我。后台回复『电子书』送你一份精选电子书大礼包,包含各类技能的优质电子书。

    展开全文
  • 0/1背包问题是学习动态规划算法最经典的例子 Java代码实现0/1背包问题 代码里有详细的注释,比较好理解
  • 动态规划介绍及其应用!
  • 自适应动态规划综述

    2017-11-09 13:40:56
    这是一篇介绍自适应动态规划的综述,里面详细介绍了离散和连续系统的动态规划方法,同时讲解了PI与VI,并给出具体的算法,还是很不错的

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 489,873
精华内容 195,949
关键字:

动态规划