DP

DP，全称为动态规划（Dynamic Programming），是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，它能够找出给定约束条件下取得最优解的分步决策过程。动态规划的核心思想是“记住已经解决的子问题”，避免重复计算，从而提高效率。动态规划的应用非常广泛，包括但不限于最短路径问题、背包问题、序列比对等。