五大算法思想（五）动态规划及常见例子

2024-07-10 02:43| 来源: 网络整理| 查看: 265

文章目录一、理论基础1.1 适用场景1.2 使用步骤1.3 常用方法-填表法1.4 经典例子二、常见例子2.1 矩阵连乘2.2 走金字塔2.3 最长公共子序列2.4 最长递增子序列2.5 0-1背包2.6 完全背包

一、理论基础

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推的方式去解决。动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子阶段，按顺序求解子阶段。与分治不同的是，在动态规划过程中，前一子问题的解，为后一子问题的求解提供了有用的信息，也就是说前后阶段的问题求解存在依赖关系。在求解任一子问题时，通过决策保留那些有可能达到最优的局部解。依次解决各子问题，最后一个子问题就是初始问题的解。以上都是官方说法，在实际运用动态规划时，每个人都有不同的理解。此处以爬楼梯问题为例，来介绍一下一种解决动态规划问题的思路。爬楼梯问题的描述：

一个人爬楼梯，一次只能爬一阶或两阶，当总共有n阶楼梯时，有多少种爬法。

本文中解决动态规划问题的思路是，确定动态规划四要素：

1、问题的阶段在该问题中，在楼梯的每层台阶上，都有着不同数量的往上爬完楼梯的可能性，也就是说每层台阶其实就意味着不同的阶段。找阶段的过程，其实就是拆分问题的过程。假如楼梯总共有10层，每次只能向上爬1层或2层楼梯。那么解决这个问题的最后一个阶段就是可以理解为从第10层楼梯往上爬（因为每次只能爬1或2层，所以这个阶段只能爬到8层或9层），再细说的话，也就是：从10层爬到9层或8层是解决该问题的第一阶段。也许有人会问，为什么要这样划分阶段？首先，在动态规划中，大问题不能像分治那样，拆分成完全相同的子问题，各子阶段是有依赖关系的，所以需要确定一个解决问题的“起点”和“终点”。而在动态规划中，“从底向上”的方案常常使用，所以此处就是从最底部（10）开始，作为解决问题的“起点”。2、每个阶段的状态在第一步中，已经对问题划分了阶段，在划分阶段后，要解决问题，还需要做的是定义阶段的状态。在该问题中，我们确定解决问题的第一个阶段是：在第10层楼梯时。在动态规划问题中，和子问题相关的各个变量的一组取值,称之为一个"状态",一个状态对应一个或多个子问题所谓的在某个状态的值,这个就是状态所对应的子问题的解,所有状态的集合称为"状态空间"。这个状态的解释比较官方，其实每个阶段的状态可以简单理解为：要用动态规划思想解决问题，需要在某个阶段定义的变量值，这个变量可以是一个变量值，也可以是一组变量值。在动态规划中，实际运用到的常常是一维数组dp[ ]或二维数组dp[ ][ ]。在爬楼梯问题中，我们就可以定义dp[10]，该变量的含义是在第10层台阶时，往上爬总共有多少种可能性。3、找数组的边界值边界值常常是动态规划方案“终点”的计算值，往往在“终点”或邻近“终点”时，才能直接计算一些变量的变化值。比如在爬楼梯问题中，从第10层楼梯，有多少种可能性，一下子是计算不出来的。但是当处在第1层或第2层楼梯时，就可以直接计算出往上爬楼梯的可能性，这就是在爬楼梯问题中的“边界值”。4、从前一个阶段转化到后一个阶段之间的递推关系前面的三个步骤都可以说是铺垫，动态规划中最核心的就是这最后一步：找状态转移方程，其实也就是每个阶段的变量怎样变化的关系式（这一步在每个问题中，都可能有不同的关系式，需要视具体情况而定）。在爬楼梯问题中，我们定义的在第10层往上爬的变量为dp[10]，此时题中有个条件是：一次只能爬一阶或两阶，这个条件就决定了转移方程的写法。因为每次只能只能爬1或2个台阶，所以，从第10层楼梯只能爬到第9层或第8层，并且在从第10层爬到第9层和从第10层爬到第8层，是不存在交叉关系的过程。处在第9层和第8层时的变量，很容易想到是dp[9]和dp[8]，所以在该问题中，从第10层往上爬的状态转移方程就是：dp[10]=dp[9]+dp[8]。在推广到后续阶段过程中，状态转移方程就是：dp[n]=dp[n-1]+dp[n-2]。 1.1 适用场景

能用动态规划解决的问题具有的特征： 1>最优化原理如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。这个特征较容易理解，常见就是在某个问题汇总存在最值。 2>无后效性即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。这个特征可以理解为：可以存储不同阶段的变量值。这样的话，在后续阶段中，就不用重复求一些之前阶段的值。 3>有重叠子问题即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势。该特征是说，解问题的不同阶段中，子问题是有重叠、依赖关系的。如果子问题不存在重叠、依赖关系，使用分治往往更好。

1.2 使用步骤

在动态规划的步骤上，每个人也有每个人的理解。一种比较容易的步骤是： 1>划分阶段按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。 2>确定状态将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。 3>确定决策并写出状态转移方程因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。 4>寻找边界条件给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

1.3 常用方法-填表法

在使用动态规划思想解决问题时，最常用的方法是填表法，该方法是以未知的量为基础，通过已知的量来刷新当前的未知量。此处借用一张网上的图来表示：由上图可知，填表法的计算过程就是：借用初始变量和状态转移方程将动态规划表逐渐填完，再找出最值。

1.4 经典例子

常见例子如下： 1>矩阵连乘 2>走金字塔 3>最长公共子序列 4>最长递增子序列 5>背包问题接下来将对这些例子进行实现，来探究动态规划的具体使用方法。

二、常见例子 2.1 矩阵连乘

矩阵连乘也是常见的动态规划例子之一。该问题的形式如下：给出N个矩阵，矩阵是有序的，即相邻矩阵之间可以进行乘法运算，求这些矩阵最小的相乘次数。矩阵乘法是满足结合律的，所以在矩阵连乘的过程中，可以有多种相乘顺序，这种相乘次序，可以用加括号来确定。如存在着下面三个维度的矩阵：A1(30 * 15)、A2(15 * 5)、A3(5 * 10)，这三个矩阵连乘时，有两种计算次序：（A1A2）A3和A1（A2A3）。以矩阵（3 * 2）和B（2 * 4）为例，两个矩阵的相乘的计算量如下：回到矩阵A1、A2、A3的矩阵连乘问题。当进行（A1A2）A3运算时，乘法计算次数为30 * 15 * 5+30 * 5 * 10=3750,；进行A1（A2A3）运算时，乘法计算次数为15 * 5 * 10+30 * 15 * 10=5250。由此可见，不同的运算顺序，会影响到乘法的计算次数。对于矩阵连乘AiAi+1Ai+2……Aj的最优解问题，假设在第k位置上找到最优解，则完整的矩阵连乘问题就变成了两个子矩阵连乘问题，即（AiAi+1……Ak）和（Ak+1……Aj）。此时用m[i][j]表示矩阵连乘的最优值，那么两个子矩阵连乘问题对应的最优值变成m[i][k],m[k+1][j]。阵连乘最优值递归式如下：此式子中的Pi-1 * Pk * Pj 代表的意思是划分后的两个矩阵的相乘后的乘法次数。矩阵相乘示例代码如下：

public class MatrixMultiplication { public static void main(String[] args) { int arr[ ] = {30,15,5,10}; int minMultiNum = getMinMultiNum(arr); System.out.println("矩阵连乘时，乘法运行的最小次数是："+minMultiNum); } private static int getMinMultiNum(int[] arr){ int minMultiNum = 0; int length = arr.length; /*存储断开位置结果*/ int[ ][ ] s = new int [length][length]; /*存储乘法计算结果*/ int[ ][ ] m = new int [length][length]; for(int i=0;i s[i][j] = 0; m[i][j] = 0; } } /*r为子问题规模*/ for(int r=2; r int j = i+r-1; /*将链ij划分为A(i)*(A[i+1:j])*/ m[i][j] = m[i+1][j] + arr[i-1]*arr[i]*arr[j]; /*s[ ][ ]存储各子问题的决策*/ s[i][j] = i; /*将链ij划分为(A[i:k])*(A[k+1:j])*/ for(int k=i+1; k m[i][j] = tmp; s[i][j] = k; } } } } minMultiNum = m[1][length-1]; return minMultiNum; } }

测试结果如下：

矩阵连乘时，乘法运行的最小次数是：3750

2.2 走金字塔

走金字塔问题也是常见的动态规划问题，该问题的形式是：有一个数字金字塔，例如：查找从最高点到底部任意处结束的路径（每一步可以从当前点走到左下方的点也可以到达右下方的点），使路径经过数字的和最大。在解该问题时，需要将数字金字塔稍微变形一下，变成下面形式：

int[ ][ ] arr = { {13}, {11,8}, {12,7,26}, {6,14,15,8}, {12,7,13,24,11} };

在按步骤解决该问题前，我们先看看这问题该怎么解。既然要求最大路径，就是求一些数的相加之和最大，同时动态规划一般是自底向上的，所以要做的第一步就是让第4层和第5层相邻的数相加，然后将相加的结果的值存储在第四层（并且此时存储的的结果与第4层原有的数的量是相同的）；再加这些相加的结果与第3层的数值再相加，存储相加结果到第3层，直到相加到了第1层，也就是最终的结果。接下来，按上面第一章节介绍的步骤来解该问题： 1>划分阶段示例中的数字金字塔有5层，那么应该划分5个阶段，还是几个阶段呢？答案是4个，因为如果划分成5个阶段的话，就是每层金字塔都代表一个阶段。这样的话，在第5层金字塔的话，最大值肯定就是24，即当层数字最大值，但这个第5层的最大值，在更新下一阶段最大值时，不具备任何意义，因为从第4层开始，求的是两个数字之和的最大值。所以，该问题需要划分为4个阶段，对应到数字金字塔上是从第1层到第4层。 2>确定状态在该问题中，每层保存一个临时最大值即可，用arr[ i ][ j ]表示。 3>写状态转移方程此时，就要运用到该题中的规则了：每一步可以从当前点走到左下方的点也可以到达右下方的点。翻译成容易理解的话就是，arr[i][j]只可能和两个值相加：arr[i+1][j]、arr[i+1][j+1]。然后比较这两种相加结果，求出较大值就行，然后也就能推导出状态转移方程了：arr[ i ][ j ] += Math.max(arr[ i+1 ][ j ], arr[ i+1 ][ j+1 ])。 4>寻找边界条件在第1步中，其实已经明确了部分边界条件“起点”，也就是从倒数第二层开始，终点也不难推导，就是第一层。有了上面的4步，就可以写代码了，示例代码如下：

public class Pyramid { public static void main(String[] args) { int[ ][ ] arr = { {13}, {11,8}, {12,7,26}, {6,14,15,8}, {12,7,13,24,11} }; int result = getMaxNum(arr); System.out.println("用迭代法求得最大数字为："+result); } private static int getMaxNum(int[][] arr){ for(int i = arr.length-2; i>=0; i--){ for(int j = 0; j for(int i = arr.length-2; i>=0; i--){ int temp = 0; for(int j = 0; j public static void main(String[] args) { String str1 = "abcd"; String str2 = "adcd"; int result = findMaxSequence(str1, str1.length(), str2, str2.length()); System.out.println("公共子序列长度是："+result); } public static int findMaxSequence(String str1, int str1length, String str2, int str2length) { int[][] dp = new int[str1length + 1][str2length + 1]; for (int i = 0; i dp[i][j] = 0; } } for (int i = 1; i if (str1.charAt(i - 1) == str2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1]; } } } System.out.println("动态规划表为:"); for (int i = 0; i System.out.print(dp[i][j]+"\t"); } System.out.println(); } return dp[str1length][str2length]; } }

测试结果：

动态规划表为: 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 2 2 0 1 2 2 3 公共子序列长度是：3

2.4 最长递增子序列

最长递增子序列也是常见的动态规划问题，该问题的形式是：一个序列中最长递增的子序列长度是多少?比如序列1、4、3、2、5，则最长的递增的子序列为1、2、5或1、3、5或1、4、5，其长度为3。该问题中，结果子序列也并不要求是相连的。其实，子序列问题都并不要求是连续的元素。在按步骤解决问题之前，我们先看看这个问题怎么解。我们首先要维护一张表，在这个表中存放的数据是：以原来序列中元素为结尾时，最长递增子序列的长度。举个例子，比如以1为最长递增子序列结尾元素时，其最长递增子序列长度为1，表中第一个元素就记录为1。以4为最长递增子序列结尾元素时，其最长递增子序列长度为2，表中第2个元素就记录为2。此时有两个问题需要注意： 1>动态规划表的第一个元素默认值是1。 2>怎么利用之前表中记录的最长递增子序列值，来推导出当前位置的最长递增子序列值？其实就是将当前位置的元素与之前位置的元素比较，如果>之前位置的元素，递增子序列长度就是在之前位置的长度+1，否则就是1，然后取较大值即可。接下来按上面第一章节介绍的步骤来解该问题： 1>划分阶段该问题阶段的划分是按元素来的，一个元素就是一个阶段。该结果所要进行的事就是将某个元素与之前位置的所有元素进行比较。 2>确定状态该问题中状态的定义是：以该位置的元素结尾，最长公共子序列的长度是多少。 3>写状态转移方程状态转移的实现方式，其实在上面已有介绍，就是当某个位置的元素大于之前位置的元素时，就取之前的最长公共子序列长度+1和默认公共子序列长度之中的较大值。示例代码如下：

if(array[i] > array[j]){ currentLegnth = Math.max(currentLegnth, dp[j]+1); }

当某位置的元素小于之前位置的所有元素时，以该位置元素结果的最终递增子序列长度就是默认值1。 4>寻找边界条件该问题的起始条件是1，也就是以最初始位置元素为结尾的默认递增子序列长度是1，结束条件就是将元素比较完。示例代码如下：

public class LongestSequence { public static void main(String[] args) { int[] array ={2,3,1,5,4}; int result = getResult(array); System.out.println("最长递增子序列长度是："+result); } private static int getResult(int[] array){ int[] dp = new int[array.length]; dp[0] = 1; for(int i = 0; i if(array[i] > array[j]){ currentLegnth = Math.max(currentLegnth, dp[j]+1); } } dp[i] = currentLegnth; } int maxLength = 1; for(int i = 0; i public static void main(String[] args) { /*商品的重量2、3、4、5*/ int[] weight = { 0 , 2 , 3 , 4 , 5 }; /*商品的价值3、4、5、6*/ int[] value = { 0 , 3 , 4 , 5 , 6 }; /*背包限重*/ int bagVeight = 8; int result = getMaxValue(weight,value,bagVeight); System.out.println("背包能装入的最大重量是："+result); } private static int getMaxValue(int[] weight,int[] value,int bagVeight){ int[][] dp = new int[weight.length][bagVeight+1]; for (int i = 1; i if (j System.out.print(dp[i][j]+" "); } System.out.println(); } return dp[weight.length-1][bagVeight]; } }

测试结果如下：

0-1背包问题，对应的动态规划表为： 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 0 0 3 4 4 7 7 7 7 0 0 3 4 5 7 8 9 9 0 0 3 4 5 7 8 9 10 背包能装入的最大重量是：10

2.6 完全背包

该问题与上一个0-1背包问题类似，所以可以直接写出类似的动态转换方程：

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]*k] + value[i]*k);

其中，k代表物品个数，k的取值范围满足的条件是：

1=5,8}; int[] weight={5,7}; int capcity = 10; int[][] dp = new int[value.length + 1][capcity + 1]; for (int i = 0; i for (int k = 0; k * weight[i] public static void main(String[] args) { /*背包容量*/ int capcity = 20; /*物品重量*/ int weight[]={2,3,4,5,9}; /*物品价值*/ int value[]={3,4,5,8,10}; /*物品个数*/ int num = weight.length; int result = getMaxValue(weight,value,capcity,num); System.out.println("能装入的最大价值为："+result); } public static int getMaxValue(int[] weight,int[] value,int capcity,int num){ int dp[] = new int[capcity+1]; for(int n=0;n System.out.println("当前重量为："+c); dp[c] = Math.max(dp[c],dp[c-weight[n]]+value[n]); } } /*输出动态规划表*/ System.out.println("完全背包问题，对应的动态规划表为："); for (int i = 0; i

【本文地址】

公司简介

联系我们