离散型动态规划常用求解方法是

离散型动态规划是指状态空间和决策集合都是离散的动态规划问题。常用的求解方法有：动态规划方程法、决策单调性法、拓扑排序法、网络流法等。

一、动态规划方程法

动态规划方程法是离散型动态规划求解的基本方法。其步骤是：定义状态，设置初始状态，建立动态规划方程，设计状态转移方程，求解最优解。这个方法适用于问题具有子结构性和最优子结构性质的问题。

以背包问题为例，设物品有n个，重量分别为w1，w2，……，wn，价值分别为v1，v2，……，vn。背包的容量为c，要求在不超过背包容量的情况下，选出若干个物品放入背包，使得背包中物品的总价值最大。

首先定义状态：f[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。

其次设置初始状态：f[0][0] = 0。

接着建立动态规划方程：f[i][j] = max{f[i-1][j], f[i-1][j-w[i]]+v[i]}。

最后求解最优解：max{f[n][j]}。

二、决策单调性法

决策单调性法是利用单调性质来求解动态规划问题的方法。对于一些具有单调性质的问题，利用决策单调性法可以大大降低问题的时间复杂度。

以数字三角形为例，设有一个数字三角形如下：

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

要求从三角形顶部走到底部，使得所经过的数字的和最大。

首先定义状态：f[i][j]表示从(i,j)顶点出发所能得到的最大和。

其次考虑状态的决策单调性：对于任意一条从顶部到底部的路径，在其上面的任意一位置(i,j)，如果我们已经知道从(i,j)出发所能获得的最大和，那么(i,j)的后继节点(i+1,j)和(i+1,j+1)只需选择其中最大的即可。

接着利用贪心思想，从顶部开始按照状态的决策单调性向下更新状态值，即可得到最优解。

三、拓扑排序法

拓扑排序法是处理有向无环图中的动态规划问题的一种方法。对于一个有向无环图，其顶点可以按照某种顺序进行排序，使得对于任意一条边(i,j)，在排序后i一定在j的前面。拓扑排序法就是利用这种排序得到动态规划的顺序，从而简化问题的复杂度。

以矩阵连乘为例，设有n个矩阵要相乘，其中第i个矩阵的行数为p[i-1]，列数为p[i]，并且满足p[i-1] = p[i-2], i>2。要求在最少计算次数的前提下求出矩阵乘积。

首先构建一个有向无环图，其中每个矩阵对应一个顶点，若矩阵i和矩阵j可以相乘，则在矩阵i对应顶点和矩阵j对应顶点之间连一条有向边，并且其边权为乘积操作的代价。

然后进行拓扑排序，得到矩阵相乘的顺序。接着，根据这个顺序，按照动态规划方程f[i][j] = min{f[i][k]+f[k+1][j]+p[i-1]p[k]p[j]}依次求解即可。

四、网络流法

网络流法是处理离散型动态规划问题的一种简单有效的方法，特别适用于需要考虑多个限制条件的问题。网络流法通过将状态抽象成节点和边，并且将限制条件抽象成容量约束，在抽象的图上求解流的最大/最小问题，从而得到问题的最优解。

以货车运输为例，设有n个城市，第i个城市有wi吨货物需要运输到其他城市，每辆货车的容量为C，每辆货车的运输费用为f，问至少需要多少辆货车才能将所有货物运输出去。

首先将每个城市抽象成一个节点，从源点s连向每个城市节点的有向边的边权为该城市需要运输的货物量，从每个城市节点连向汇点t的有向边的边权为C。然后将在同一辆货车中运输的货物抽象成容量为C的边，并且将边权设为f。最后求解从源点到汇点的最大流，所需要的流量即为至少需要的货车数量，运输的总费用为最大流的值乘以f。