动态规划详解

2023-10-12 07:42| 来源: 网络整理| 查看: 265

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

1.动态规划的由来

现状：在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。

多阶段决策问题：因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。

动态规划：在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法。（源自：百度百科）

2.动态规划与分治算法的区别

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

问题：与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

分析：如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。

解决：我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式

3.动态规划应该怎样做？

（1）解决存储问题，找出数组元素的含义，刻画一个最优解的结构特征（2）找出元素之间的递推式，递归地定义最优解的值（3）寻找初始值，计算最优解的值，按顺序从小到大算（自底向上）（4）利用计算出的信息构造一个最优解（需要维护额外信息）

4.动态规划有哪些应用？（1）硬币使用最少

问题：假设你有2元、5元、7元三种硬币，每种硬币无限多，问购买27元的物品最少需要多少枚硬币？

分析：（1）虽然我不知道最优策略是什么，但最优策略肯定是a1,a2,…ak面值加起来是27，其中a1,a2,…ak代表各个硬币的状态，k代表使用的硬币数。“最少需要多少枚硬币”的意思是说，我们需要达到的最优效果是让k的值最小。

可以想象，在连续的硬币组合选择中，我们需要做不同的决策，即多阶段决策。对于此问题的某个阶段的状态，状态的含义有：此时硬币的面值总数以及硬币数k。

（2）接下来找出递推式。考虑最后一步，一定有一枚最后的硬币ak，除掉这个硬币，前面硬币面值加起来是27-ak。因为是采取最优策略，前面拼出27-ak的硬币数k-1一定最少，否则不是最优策略。可以用反证法，如果k-1枚更多或更少，则k枚也将变化，不是最优。也即原问题缩小规模后的子问题，依然要最优解，所以是最优化问题。

根据最后那枚硬币ak是多少？可将原问题分解为三部分，硬币只可能是2或5或7，根据分解的问题合并，找到最小的值。

f(27) = min{f(27-2)+1,f(27-5)+1,f(27-7)+1}

其中，函数f（x）的含义是最少用多少枚硬币拼出X （3）找出初始值。考虑初始条件和边界情况，如果X-2,X-5或X-7小于0怎么办？什么时候停下来？如果不能拼出Y，就定义f[Y]=正无穷。

用转移方程算不出来，就需要手工定义初始条件，初始条件：f[0]=0

（4）计算顺序从大到小算f[27]，还是从f[0]开始计算？当采用递归算法时，我们从大到小进行计算，但是面临了很多重复计算。采用动态规划算法时，我们从小到大进行计算，我们将算过的子问题通过数组存储起来，当需要时进行查找存储值就可以了，不需要重复计算。例如，当我们计算左边的f[x]时，f[x-2]等等已经计算出来了。

public static void main(String[] args) { int n = 27; System.out.println("购买"+n+"元物品，最少需要"+f(n)+"枚硬币"); System.out.println("购买"+n+"元物品，最少需要"+f2(n)+"枚硬币"); //购买27元物品，最少需要5枚硬币 } //1.递归算法 public static int f(int n) { //初始值 if(n == 0) return 0; //因为最大值+1后变成负数，这里需要减1 int res = Integer.MAX_VALUE-1; if(n >= 2){ res = Math.min(f(n-2)+1, res);} if(n >= 5){ res = Math.min(f(n-5)+1, res);} if(n >= 7){ res = Math.min(f(n-7)+1, res);} return res; } //2.动态规划算法 public static int f2(int n) { int[] dp = new int[n+1]; dp[0] = 0; for(int i=1;i res = Math.min(dp[i-2]+1, res);} if(i >= 5){ res = Math.min(dp[i-5]+1, res);} if(i >= 7){ res = Math.min(dp[i-7]+1, res);} dp[i] = res; } return dp[n]; }

总结：对于该问题，我们很容易想到是一系列硬币组合成了27元。关键是要立马想到如何将该问题分解为规模更小的子问题。难点在于“如何求解出递推式”以及某一阶段所代表的含义。

因此需要梳理一下某一阶段的状态，某一阶段已知的客观条件有该阶段的硬币组合面值，需要求解的是最优策略时的最少硬币数。有时，需要知道使用最少硬币购买物品时的硬币组合，而这个问题不需要考虑。所以，我们不需要去维护这个额外信息。因此，我们可以用f(X)来代表这个状态，X是已知的硬币总面值，代表的含义是硬币最少达到X的硬币数。

对于递推式，我们在问题的分解和合并中，进行求解。此问题，将原问题分为三种情况，然后再求最小值，进行子问题的合并。最后，自然就能推出递推式。

细节方面，注意多种情况如何求解最值，我们需要引入中间值进行存储最值。在定义数组元素时，可以把数组元素用作中间值。同时，中间值要存储最大值，在java中最大值+1又会变成负数，造成错误。可以把最大值减1，进行处理，也可以在if中进行条件判断过滤。不能忘记，设置初始值，注意控制边界，设置结束条件。

一般用数组存储中间计算的结果，根据上述代码可见，动态规划算法与分治算法很类似，但是去除了重复计算的过程，大大提高了运算速度。

（2）青蛙跳台阶

问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个7级的台阶总共有多少种跳法。

分析：（1）根据前面的例子，可以立马想到。对于青蛙所处的状态，某一阶段已知青蛙所处的台阶，然后求解跳到该台阶的多少种跳法。因为，不需要知道各个跳法是怎么跳的，也即不需要维护这个额外信息。因此，可以直接用数组dp[n]来表达这个状态，含义是跳到第n级台阶时的跳法种数。

（2）求解递推式。将原问题进行分解和合并，青蛙跳到第n级时，分两种情况，前面青蛙可以从n-1跳1级，也可以从n-2时跳2级，跳法种数是两者之和。因此，得出递推式： dp[n] = dp[n-1]+dp[n-2]

（3）找出初始值，显然，青蛙在第0级时算0种跳法，在第1级时只能跳1步，算1种跳法。 dp[0] = 0;dp[1] = 1;dp[1] = 2;

public static void main(String[] args) { int n = 7; System.out.println("跳到第"+n+"级台阶时，有"+f(n)+"种跳法"); //跳到第7级台阶时，有21种跳法 } public static int f(int n) { //创建数组进行保存 int[] dp = new int[n+1]; //给出初始值 dp[0] = 0; dp[1] = 1; // 通过关系式来计算出 dp[n] for(int i=2;i int n = 7; System.out.println("跳到第"+n+"级台阶时，有"+f(n)+"种跳法"); //跳到第7级台阶时，有21种跳法 } public static int f(int n) { //创建数组进行保存 int[] dp = new int[n+1]; //给出初始值 dp[0] = 0; dp[1] = 1; dp[2] = 2; // 通过关系式来计算出 dp[n] for(int i=3;i int m = 7,n=3; System.out.println("对于"+m+"×"+n+"的网格，机器人有"+f(m,n)+"种走法"); //对于7×3的网格，机器人有12种走法 } public static int f(int m,int n) { //创建数组存储值 int[][] dp = new int[m][n]; //初始值 dp[0][0] = 0; dp[1][0] = 1; dp[0][1] = 1; //递推式 for(int i=1;i dp[i][j] = dp [i-1][j] + dp[i][j-1]; } } //返回值 return dp[m-1][n-1]; }

总结：注意初始值，对于往右一排和往下一排只有一种走法，上面的示例代码没有考虑到。

public static void main(String[] args) { int m = 7,n=3; System.out.println("对于"+m+"×"+n+"的网格，机器人有"+f(m,n)+"种走法"); //对于7×3的网格，机器人有28种走法 } public static int f(int m,int n) { int[][] dp = new int[m][n]; //初始值 dp[0][0] = 0; for(int i = 0; i dp[0][i] = 1; } //递推式 for(int i=1;i dp[i][j] = dp [i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; } 5.动态规划的术语

（1）把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同。描述阶段的变量称为阶段变量。

（2）状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。例如，状态可以是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。

（3）如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。换句话说，过程的每一次实现可以用一个状态序列表示。例如，每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。

（4）一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多问题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。

（5）由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。

（6）给定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阶段的状态转移规律，称为状态转移方程。

（7）作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略” 。最优性原理实际上是要求问题的最优策略的子策略也是最优。问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解，这样的问题称为最优化问题。

6.如何识别需要使用动态规划算法的问题？

1.计数问题

有多少种方式走到右下角

有多少种方法选出k个数使得和是sum

2.最值问题

从左上角走到右下角路径的最大数字和最长上升子序列长度

3.求存在性问题

取石子游戏，先手是否必胜能不能去除k个数使得和是sum

6.动态规划和递归的优劣

. 计数问题最值问题

【本文地址】

公司简介

联系我们