什么是动态规划？

动态规划（DP）是一种算法技术，它通过将优化问题拆分成更简单的子问题，并重复利用这些子问题的解来解决原问题。

DP 常用于可以用更小子问题递归表示其解的问题。这种技术被称为“动态”，因为子问题的解可以存储起来并重复利用，以解决更大的问题，因此比从头开始直接解决大问题更高效。

DP 可用于多种问题，例如最短路径、最长公共子序列和最大子数组。当问题具有重叠子问题和最优子结构时，DP 尤其有用。这意味着可以根据子问题的最优解构造出原问题的最优解。