动态规划算法的分类

动态规划（Dynamic Programming，DP）算法，又称动态递推法，是将原问题分解成若干个相互重叠的子问题，通过子问题的解的组合来解决原问题。它通常适用于具有重复子问题和最优子结构性质的问题，是一种自下而上的求解方法。本文将从多个角度分析动态规划算法的分类。

1.按优化目标的不同分类

动态规划问题的优化目标因问题而异，从而，根据不同的优化目标可以将动态规划问题分类为最大化优化和最小化优化两种。

最大化优化是指通过变量的选择，使得目标函数的值达到最大。例如，最长递增子序列（LIS）问题、最大子数组和问题（Maximum Subarray Problem）等。

最小化优化是指通过变量的选择，使得目标函数的值达到最小。例如，最短路径（Shortest Path）问题，编辑距离（Edit Distance）问题等。

2.按阶段数的不同分类

动态规划问题根据阶段的数目不同，可以分为两类：单阶段动态规划问题和多阶段动态规划问题。

单阶段动态规划问题是指不需要考虑顺序的动态规划问题。例如，最大的连续子数组和问题是没有阶段之分的，此问题可以看成整个数组就是一个阶段。

多阶段动态规化问题是指一个问题按顺序可以划分为若干个阶段，每个阶段的决策都受到之前阶段决策的影响。例如，工程上的项目管理就是一个典型的多阶段决策问题，因为每个工作包会被划分为多个阶段。

3.按是否需要记录路径分类

动态规划问题可以需要记录路径，也可以不需要记录路径。需要记录路径通常是需要返回最优解时，用于记录到达这个最优解时的路径，例如在最短路径问题中解决了最短路问题，还需要确定哪条路径最短。

不需要记录路径，问题只需要得到最优解。例如，在最长递增子序列（LIS）问题中，只需要求最长递增子序列的长度，而不需要求出最长递增子序列本身。

总之，动态规划算法是一种十分实用和有效的求解算法，它利用了子问题性质，将问题简化为多个重叠的子问题，通过组合子问题的解来求解原问题。根据不同的分类方法，可以将动态规划问题分类为最大化优化和最小化优化动态规划问题、单阶段动态规划问题和多阶段动态规划问题以及需要记录路径或者不需要记录路径的动态规划问题。