一维动态规划

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