一维动态规划

动态规划是将一个问题分解为重叠子问题、每个子问题只求解一次并存储结果以避免重复计算的技术。在一维 DP 中，每个状态只依赖于固定数量的前序状态，因此解法是从左到右构建一个数组。第一步总是确定递推关系：位置 i 的答案依赖于什么？这里的问题涵盖你会反复遇到的核心 DP 模式：线性序列、背包决策和字符串分割。DP 问题以难以识别著称，提高的唯一可靠方法是多做题并研究其递推结构。