什么样的题用动态规划

动态规划是一种常用的求解优化问题的方法，其主要应用领域包括计算机视觉、自然语言处理、机器学习、网络流量控制等。在这个过程中，选择动态规划算法通常会提高问题的解决效率，这篇文章将从多个角度解释什么样的题用动态规划，并最后给出全文摘要和3个关键词。

首先，动态规划通常应用于具有最优子结构的问题，即问题的整体最优解可以通过子问题的局部最优解来推导出来。例如，最大子数组问题和0-1背包问题就是具有最优子结构的问题，便于用动态规划求解。

其次，动态规划算法还适用于无后效性的问题，即一个状态的状态值不仅仅只与上一个状态有关，还受到之前状态的影响。比如，在求矩阵链乘积问题时，前一个状态的求解难度取决于之前合并的两个矩阵的大小，因此需要考虑之前的状态对于当前状态的影响。

此外，动态规划还适用于可以通过两种方法解决的问题：自顶向下或自底向上。如果按照从初始值不断向上推导状态值的方法进行，则称之为自顶向下。如果按照从小问题向大问题解决的方式，则称之为自底向上。例如，在计算斐波那契数列时，可以通过分别计算 f(n-1) 和 f(n-2) 的方法从顶部开始计算。这种方法在计算大型数据时可能会产生重复计算，所以另一种方法是从底部开始解决，通过计算 f(1) 和 f(2) 来计算 f(n) 。

最后，在一些能够转换成最长公共子序列或最长上升子序列等问题时，可以尝试用动态规划解决，因为这些问题正好符合了动态规划的必要条件：最优解的子结构和子问题之间的重叠字问题，例如在编辑距离问题中，需要求出两个字符串之间的最小编辑距离，需要将问题转换成最长公共子序列问题进行求解。

总体而言，以上是什么样的题用动态规划的几种常见情况。选择动态规划算法时需要综合考虑问题的复杂性以及算法本身的复杂度，并根据问题的特征进行选择。