动态规划问题常见解法

什么是动态规划算法，常见的动态规划问题分析与求解理解动态规划动态规划中递推式的求解⽅法不是动态规划的本质。

我曾经给学校参加NOIP的同学多次讲过动态规划，我试着讲⼀下我理解的动态规划，争取深⼊浅出。

希望你看了我的答案，能够喜欢上动态规划。

0. 动态规划的本质，是对问题状态的定义和状态转移⽅程的定义。

引⾃维基百科dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的⽅式去解决。

本题下的其他答案，⼤多都是在说递推的求解⽅法，但如何拆分问题，才是动态规划的核⼼。

⽽拆分问题，靠的就是状态的定义和状态转移⽅程的定义。

1. 什么是状态的定义？⾸先想说⼤家千万不要被下⾯的数学式吓到，这⾥只涉及到了函数相关的知识。

我们先来看⼀个动态规划的教学必备题：给定⼀个数列，长度为N，求这个数列的最长上升（递增）⼦数列（LIS）的长度.以 1 7 2 8 3 4 为例。

这个数列的最长递增⼦数列是 1 2 3 4，长度为4；次长的长度为3，包括 1 7 8; 1 2 3 等.要解决这个问题，我们⾸先要定义这个问题和这个问题的⼦问题。

有⼈可能会问了，题⽬都已经在这了，我们还需定义这个问题吗？需要，原因就是这个问题在字⾯上看，找不出⼦问题，⽽没有⼦问题，这个题⽬就没办法解决。

所以我们来重新定义这个问题：给定⼀个数列，长度为N，设为：以数列中第k项结尾的最长递增⼦序列的长度.求中的最⼤值.显然，这个新问题与原问题等价。

⽽对于来讲，都是的⼦问题：因为以第k项结尾的最长递增⼦序列（下称LIS），包含着以第中某项结尾的LIS。

上述的新问题也可以叫做状态，定义中的“为数列中第k项结尾的LIS的长度”，就叫做对状态的定义。

动态规划1．最短路线问题解（1）：将上图该画成下图：记a （1,2）=4，a(1,3)=5，依次类推，表示每个点和值的关系。

逆序递推方程：⎪⎩⎪⎨⎧==+++=0)6(61,2,3,4,5)}1(1),({min )(s f k k s k f k u k s k d k uk s k fAB 1B 2C 1 C 2C 3 C 4D 1D 2 D 3E 1 E 2F4523 6 8 7 75845348435 6 2 314 31234 5 6 789 101112134523 6 8 7 7584534 8435 6 2 314 3如图各状态：逆序递推，找出上一个状态到下一阶段的最小路径值。

例如，当K=4时，状态 它们到F 点需经过中途 点E ，需一一分析从E 到 F 的最短路：先说从D1到F 的最短路 有两种选择：经过 E1, E2, 比较最短。

这说明由 D1 到F 的最短距离为7，其路径为AB 1B 2C 1 C 2C 3 C 4D 1 D 2 D 3E 1 E 2F4523 6 87 75845348435 62 31 4 3第1阶段 第2阶段 第3阶段 第4阶段 第5阶段状态 1状态 2状态3状态 4状态 5状态 6)}(),(),(),(m in{)(252141511414E f E D d E f E D d D f ++=.7}35,43min{=++=.11F E D →→},,{3214D D D S =a=[0,4,5,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf 4,0,inf,2,3,6,inf,inf,inf,inf,inf,inf,inf 5,inf,0,inf,8,7,7,inf,inf,inf,inf,inf,inf inf,2,inf,0,inf,inf,inf,5,8,inf,inf,inf,inf inf,3,8,inf,0,inf,inf,4,5,inf,inf,inf,inf inf,6,7,inf,inf,0,inf,inf,3,4,inf,inf,inf inf,inf,7,inf,inf,inf,0,inf,8,4,inf,inf,inf inf,inf,5,4,inf,inf,inf,0,inf,inf,3,5,inf inf,inf,inf,8,5,3,8,inf,0,inf,6,2,inf inf,inf,inf,inf,inf,4,4,inf,inf,0,1,3,inf inf,inf,inf,inf,inf,inf,inf,3,6,1,0,inf,4 inf,inf,inf,inf,inf,inf,inf,5,2,3,inf,0,3 inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,4,3,0]; s8=min(a(8,11)+a(11,13),a(8,12)+a(12,13)); s9=min(a(9,11)+a(11,13),a(9,12)+a(12,13)); s10=min(a(10,11)+a(11,13),a(10,12)+a(12,13)); s4=min(a(4,8)+s8,a(4,9)+s9); s5=min(a(5,8)+s8,a(5,9)+s9); s6=min(a(6,9)+s9,a(6,10)+s10); s7=min(a(7,9)+s9,a(7,10)+s10); s2=[a(2,4)+s4,a(2,5)+s5,a(2,6)+s6]; s2=min(s2);s3=[a(3,5)+s5,a(3,6)+s6,a(3,7)+s7]; s3=min(s3);s1=min(a(1,2)+s2,a(1,3)+s3)运行结果为：s8 = 7 s9 = 5 s10 = 5 s4 = 12 s5 = 10 s6 = 8 s7 = 9 s2 =13s3 = 15 s1 = 17结果分析：s 表示每个点到终点的最短距离，那么最短路程为17。

动态规划解法总结总结以下刚做完的，题⽬和彩⾊图⽚均出⾃此题集。

规划问题就是在⼀定约束下寻找最优解，最优解是某种价值的最⼤（⼩）化，⽽这种价值⼀定是在某种变动之中累计的，这才需要规划，⽐如说青蛙跳台阶问题，⼀次可以跳⼀格，也可以跳两格；⽐如说礼物的最⼤价值问题，每次移动可以向左也可以向右；这种变动总是可以描述为：物体从起始位置向其他位置移动，价值在经过任意位置时会发⽣改变，且移动过程中有若⼲路径可以选择。

因此解决规划问题的关键就是寻找价值随着位置改变⽽改变的规律，从⽽选择最终价值最⼤的路径。

这种规律性被总结为动态规划的思想，我总结就是倒着想，正着解。

倒着想是指：物体移动到最终位置前⼀步可以位于哪⼏个位置？移动到这⼏个位置的最优解和移动到最终位置的最优解之间是否有函数关系f(x)？物体从起始位置移动到哪些位置的路径是唯⼀的？有唯⼀路径的位置的价值和从起点到其周边位置的最优解是否也满⾜函数关系f(x)?如果⼆、四成⽴，则f(x)就是状态转移⽅程（状态定义为到达某⼀位置的最优解），三则是找到了我们可以依赖的起点，从起点经过状态转移⽅程就能找打到达任意位置的最优路径，这就是正着解。

我将我做过的动态规划问题总结为三类，总体做法是类似的，第⼀题详细讲倒着想，正着解的求解思路。

第⼀类动态规划问题——终点固定1. 礼物的最⼤价值在⼀个 m*n 的棋盘的每⼀格都放有⼀个礼物，每个礼物都有⼀定的价值（价值⼤于 0）。

你可以从棋盘的左上⾓开始拿格⼦⾥的礼物，并每次向右或者向下移动⼀格、直到到达棋盘的右下⾓。

给定⼀个棋盘及其上⾯的礼物的价值，请计算你最多能拿到多少价值的礼物？输⼊:[[1,3,1],[1,5,1],[4,2,1]]输出: 12解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物倒着想：到达最右下⾓前有两步，其上⽅和其左侧最右下⾓的上⽅和左侧的最优解和最终最优解的关系也很显然，两条路径的价值中⼤者即为到达最右下⾓的最优解到达第⼀⾏、第⼀列的任意位置的路径是唯⼀的第⼆条发现的规则显然是适⽤于到达任意位置的因此，这道题可以很容易写出状态转移⽅程有了状态转移⽅程和初始状态，就可以正着解，也就是在第⼀⾏、第⼀列所有位置的最⼤价值已知的情况下，由状态转移⽅程依次计算出每⾏从左到右所有位置的最优解（这样就能保证每个位置求解时其上、右⽅位置最优解已被解出）。

动态规划典型案例解析及计算过程梳理动态规划（Dynamic Programming）是一种通过将问题分解为子问题来解决复杂问题的算法策略。

它通常用于优化问题，通过将问题的解决方案划分为相互重叠的子问题来降低计算复杂度。

下面将通过几个典型案例，详细解析动态规划的应用及其计算过程。

1. 斐波那契数列斐波那契数列是一种经典的动态规划问题。

它的定义是：F(n) =F(n-1) + F(n-2)，其中F(0) = 0，F(1) = 1。

我们需要计算第n个斐波那契数。

通过动态规划的思想，可以将该问题划分为子问题，即计算第n-1和第n-2个斐波那契数。

可以使用一个数组来保存已经计算过的斐波那契数，避免重复计算。

具体的计算过程如下：1. 初始化一个长度为n+1的数组fib，将fib[0]设置为0，fib[1]设置为1。

2. 从i=2开始遍历到n，对于每个i，计算fib[i] = fib[i-1] + fib[i-2]。

3. 返回fib[n]作为结果。

通过上述过程，我们可以快速地得到第n个斐波那契数。

这个案例展示了动态规划的重要特性，即将问题分解为子问题进行求解，并利用已经计算过的结果来避免重复计算。

2. 背包问题背包问题是另一个常见的动态规划问题。

问题的定义是：有一组物品，每个物品有自己的重量和价值，在限定的背包容量下，如何选择物品使得背包中的总价值最大化。

通过动态规划的思想，背包问题可以被划分为子问题。

我们可以定义一个二维数组dp，其中dp[i][j]表示在前i个物品中，背包容量为j时的最大价值。

具体的计算过程如下：1. 初始化一个大小为n+1行，m+1列的二维数组dp，其中n为物品数量，m为背包容量。

将所有元素初始化为0。

2. 从i=1开始遍历到n，对于每个i，从j=1开始遍历到m，对于每个j，进行如下判断：- 若当前物品的重量大于背包容量j，则dp[i][j] = dp[i-1][j]，即不选择当前物品；- 若当前物品的重量小于等于背包容量j，则dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)，即选择当前物品或不选择当前物品所能获得的最大价值。

动态规划问题常见解法
动态规划是一种高效解决优化问题的方法。

它通常用于涉及最
优化问题和最短路径的计算中。

下面是一些常见的动态规划问题解法：
1. 背包问题
背包问题是动态规划中的经典问题之一。

其目标是在给定的背
包容量下，选择一些物品放入背包中，使得物品总价值最大。

解决
这个问题的常见方法是使用动态规划的思想，定义一个二维数组来
记录每个物品放入背包时的最大价值，然后逐步计算出最终的结果。

2. 最长公共子序列问题
最长公共子序列问题是寻找两个字符串中最长的公共子序列的
问题。

解决这个问题的常见方法是使用动态规划的思想，定义一个
二维数组来记录两个字符串中每个位置的最长公共子序列的长度。

然后通过递推关系来计算出最终的结果。

3. 矩阵链乘法问题
矩阵链乘法问题是计算一系列矩阵相乘的最佳顺序的问题。

解
决这个问题的常见方法是使用动态规划的思想，定义一个二维数组
来记录每个矩阵相乘时的最小乘法次数，然后逐步计算出最终的结果。

4. 最长递增子序列问题
最长递增子序列问题是寻找一个序列中最长的递增子序列的问题。

解决这个问题的常见方法是使用动态规划的思想，定义一个一
维数组来记录每个位置处的最长递增子序列的长度，然后通过递推
关系来计算出最终的结果。

以上是一些常见的动态规划问题解法。

通过灵活运用这些方法，我们可以更高效地解决优化问题和最短路径计算等相关任务。

常见的动态规划问题分析与求解 转载⾃：动态规划（Dynamic Programming，简称DP），虽然抽象后进⾏求解的思路并不复杂，但具体的形式千差万别，找出问题的⼦结构以及通过⼦结构重新构造最优解的过程很难统⼀，并不像回溯法具有解决绝⼤多数问题的框架（)。

为了解决动态规划问题，只能靠多练习、多思考了。

本⽂主要是对⼀些常见的动态规划题⽬的收集，希望能有所帮助。

难度评级受个⼈主观影响较⼤，仅供参考。

⽬录（点击跳转）动态规划求解的⼀般思路： 判断问题的⼦结构（也可看作状态），当具有最优⼦结构时，动态规划可能适⽤。

求解重叠⼦问题。

⼀个递归算法不断地调⽤同⼀问题，递归可以转化为查表从⽽利⽤⼦问题的解。

分治法则不同，每次递归都产⽣新的问题。

重新构造⼀个最优解。

备忘录法： 动态规划的⼀种变形，使⽤⾃顶向下的策略，更像递归算法。

初始化时表中填⼊⼀个特殊值表⽰待填⼊，当递归算法第⼀次遇到⼀个⼦问题时，计算并填表；以后每次遇到时只需返回以前填⼊的值。

实例可以参照矩阵链乘法部分。

1.硬币找零难度评级：★ 假设有⼏种硬币，如1、3、5，并且数量⽆限。

请找出能够组成某个数⽬的找零所使⽤最少的硬币数。

解法： ⽤待找零的数值k描述⼦结构/状态，记作sum[k]，其值为所需的最⼩硬币数。

对于不同的硬币⾯值coin[0...n]，有sum[k] = min(sum[k-coin[0]] , sum[k-coin[1]], ...)+1。

对应于给定数⽬的找零total，需要求解sum[total]的值。

typedef struct {int nCoin; //使⽤硬币数量//以下两个成员是为了便于构造出求解过程的展⽰int lastSum;//上⼀个状态int addCoin;//从上⼀个状态达到当前状态所⽤的硬币种类} state;state *sum = malloc(sizeof(state)*(total+1));//initfor(i=0;i<=total;i++)sum[i].nCoin = INF;sum[0].nCoin = 0;sum[0].lastSum = 0;for(i=1;i<=total;i++)for(j=0;j<n;j++)if(i-coin[j]>=0 && sum[i-coin[j]].nCoin+1<sum[i].nCoin){sum[i].nCoin = sum[i-coin[j]].nCoin+1;sum[i].lastSum = j;sum[i].addCoin = coin[j];}if(sum[total].nCoin == INF){printf("can't make change.\n");return 0;}else//output ; 通过sum[total].lastSum和sum[total].addCoin，很容易通过循环逆序地或者编写递归调⽤的函数正序地输出从结束状态到开始状态使⽤的硬币种类。

动态规划算法的常见实例动态规划算法是一种将复杂问题分解为简单子问题来解决的算法，它可被应用于多个领域中，如经济学、生物学、计算机科学等。

在本文中，我们将详细讨论动态规划算法的常见实例。

一、最长公共子序列问题最长公共子序列（LCS）问题是一个经典的计算机科学问题，它要求在两个字符串中找到最长的相同连续子序列。

例如，对于字符串“ABCD”和“ACDF”，最长公共子序列为“ACD”。

使用动态规划方法来解决LCS问题。

首先定义一个m行n列的二维矩阵，其中m和n分别表示两个字符串的长度。

然后，使用以下递推关系：1. 如果一个字符串的长度为0，LCS为0。

2. 如果两个字符不相同，则LCS为它们的前一个字符集合和它们的后一个字符集合的最大值。

3. 如果两个字符相同，则LCS为它们的前一个字符集合和它们的后一个字符集合所组成的子序列中的最大值加1。

最后，矩阵右下角的值就是LCS的长度。

二、背包问题背包问题（Knapsack problem）是一个经典的组合优化问题，被广泛应用于计算机科学和其他领域。

在一个决策者必须决定是否将某些物品放入背包中的场景中，背包问题就发挥了作用。

具体来说，我们要解决的问题是：对于一个固定容量的背包，有一些物品，它们的重量和价值都不同，如何在不超过背包容量的前提下，使所装载物品的总价值最大化。

一种解决方案是使用动态规划方法。

定义一个二维数组，其行表示物品，列表示背包大小。

然后，使用以下递推关系：1. 如果所考虑的物品重量大于背包容量，则不选此物品。

2. 否则，在选取该物品和不选该物品两种情况中选择最优解作为最终结果。

最后，矩阵中右下角的值就是最大的总价值。

三、矩阵链乘法矩阵链乘法是一种计算矩阵乘积的优化算法。

它使用动态规划算法来确定矩阵乘积的最小值。

对于一个长度为n的矩阵链，我们可以定义一个n×n 的矩阵M，其中第i行第j列的元素Mi，j表示第i个矩阵与第j个矩阵相乘的最小次数。

数学建模中的动态规划问题动态规划是一种常见且重要的数学建模技术，它在解决许多实际问题中发挥着关键作用。

本文将介绍动态规划问题的基本概念和解题方法，并通过几个实例来说明其在数学建模中的应用。

一、动态规划的基本概念动态规划是解决多阶段决策问题的一种方法。

一般来说，动态规划问题可以分为以下几个步骤：1. 确定阶段：将问题划分为若干个阶段，每个阶段对应一个决策。

2. 确定状态：将每个阶段的可能状态列出，并定义对应的决策集合。

3. 确定状态转移方程：根据当前阶段的状态和上一个阶段的决策，确定状态的转移关系。

4. 确定初始条件：确定问题的初始状态。

5. 确定决策的评价标准：根据问题的具体要求，确定决策的评价标准。

6. 使用递推或递归公式求解：根据状态转移方程，使用递推或递归公式求解问题。

二、动态规划问题的解题方法在解决动态规划问题时，一般可以使用自顶向下和自底向上两种方法。

自顶向下的方法，也称为记忆化搜索，是指从问题的最优解出发，逐步向下求解子问题的最优解。

该方法通常使用递归来实现，并通过记忆化技术来避免重复计算。

自底向上的方法，也称为动态规划的迭代求解法，是指从问题的初始状态出发，逐步向上求解各个阶段的最优解。

该方法通常使用迭代循环来实现，并通过存储中间结果来避免重复计算。

三、动态规划在数学建模中的应用1. 01背包问题：给定一组物品和一个背包，每个物品有对应的价值和重量，要求选择一些物品放入背包中，使得背包中物品的总价值最大，而且总重量不超过背包的容量。

这是一个经典的动态规划问题，在数学建模中经常遇到。

2. 最短路径问题：在给定的有向图中，求解从一个顶点到另一个顶点的最短路径。

该问题可以使用动态规划的思想对其进行求解，其中每个阶段表示到达某个顶点的最短路径。

3. 最长公共子序列问题：给定两个序列，求解它们最长的公共子序列的长度。

该问题可以使用动态规划的方法解决，其中每个阶段表示两个序列的某个子序列。

四、实例分析以01背包问题为例进行具体分析。

动态规划问题典型解决策略概述动态规划（Dynamic Programming）是一种常见的算法设计方法，用于求解多阶段决策问题。

通过将问题划分为若干个子问题，并保存已解决子问题的结果，最终得到原问题的解。

本文将对动态规划问题的典型解决策略进行概述。

一、动态规划基本思想动态规划算法的基本思想是将原问题分解为若干个子问题，通过求解子问题的最优解，得到原问题的解。

其核心是利用子问题的最优解构造原问题的最优解，以此达到减少计算量的目的。

二、动态规划问题的特点动态规划问题具有以下几个特点：1. 最优子结构性质：原问题的最优解可以通过子问题的最优解构造而得到。

2. 重叠子问题性质：动态规划算法会将子问题的解保存在一个表或数组中，避免重复计算相同的子问题。

3. 状态转移方程：通过定义状态转移方程来描述原问题与子问题之间的关系，进而求解问题的最优解。

三、动态规划问题的解决策略为了解决动态规划问题，需要采用合适的解决策略。

下面介绍几种常见的动态规划问题解决策略。

1. 自顶向下的递归求解这种方法是从原问题开始，不断分解为规模更小的子问题，并递归地求解子问题。

通过保存已解决子问题的结果，避免重复计算，提高效率。

这种方法常用于问题规模较小、子问题数较少的情况。

2. 自底向上的迭代求解自底向上的方法是从问题的较小规模开始解决，逐步构造出问题的最优解。

按顺序求解子问题，通过已解决问题的最优解计算出更大规模的问题的最优解。

这种方法适用于问题规模较大、子问题之间没有重叠的情况。

3. 带备忘录的自顶向下求解带备忘录的自顶向下方法在递归求解的基础上，增加了备忘录来保存已解决子问题的结果。

在每次递归时，先查看备忘录中是否已经计算过，如果有则直接使用，避免重复计算。

这种方法常用于问题规模较大、子问题数较多的情况。

4. 状态压缩状态压缩是指通过定义合适的状态表示，将问题的状态空间进行压缩。

通过降低空间复杂度来提高程序的效率。

这种方法常用于状态空间较大的问题，如旅行商问题等。

动态规划算法详解及经典例题⼀、基本概念（1）⼀种使⽤多阶段决策过程最优的通⽤⽅法。

（2）动态规划过程是：每次决策依赖于当前状态，⼜随即引起状态的转移。

⼀个决策序列就是在变化的状态中产⽣出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

假设问题是由交叠的⼦问题所构成，我们就能够⽤动态规划技术来解决它。

⼀般来说，这种⼦问题出⾃对给定问题求解的递推关系中，这个递推关系包括了同样问题的更⼩⼦问题的解。

动态规划法建议，与其对交叠⼦问题⼀次重新的求解，不如把每⼀个较⼩⼦问题仅仅求解⼀次并把结果记录在表中（动态规划也是空间换时间的）。

这样就能够从表中得到原始问题的解。

（3）动态规划经常常使⽤于解决最优化问题，这些问题多表现为多阶段决策。

关于多阶段决策：在实际中，⼈们经常遇到这样⼀类决策问题，即因为过程的特殊性，能够将决策的全过程根据时间或空间划分若⼲个联系的阶段。

⽽在各阶段中。

⼈们都须要作出⽅案的选择。

我们称之为决策。

⽽且当⼀个阶段的决策之后，经常影响到下⼀个阶段的决策，从⽽影响整个过程的活动。

这样，各个阶段所确定的决策就构成⼀个决策序列，常称之为策略。

因为各个阶段可供选择的决策往往不⽌⼀个。

因⽽就可能有很多决策以供选择，这些可供选择的策略构成⼀个集合，我们称之为同意策略集合（简称策略集合）。

每⼀个策略都对应地确定⼀种活动的效果。

我们假定这个效果能够⽤数量来衡量。

因为不同的策略经常导致不同的效果，因此，怎样在同意策略集合中选择⼀个策略，使其在预定的标准下达到最好的效果。

经常是⼈们所关⼼的问题。

我们称这种策略为最优策略，这类问题就称为多阶段决策问题。

（4）多阶段决策问题举例：机器负荷分配问题某种机器能够在⾼低两种不同的负荷下进⾏⽣产。

在⾼负荷下⽣产时。

产品的年产量g和投⼊⽣产的机器数量x的关系为g=g(x)，这时的年完善率为a，即假设年初完善机器数为x，到年终时完善的机器数为a*x(0<a<1)；在低负荷下⽣产时，产品的年产量h和投⼊⽣产的机器数量y的关系为h=h(y)。