动态规划求解策略：公交接客与最长上升子序列

动态规划是一种在数学优化中用于求解最优化问题的方法，通过把原问题分解成相互重叠的子问题，然后存储子问题的解来避免重复计算。在给定的PPT中，主要讨论了如何运用动态规划解决特定问题。 首先，提到的是动态规划的一般模型，包括坐标型、线性型、背包型、区间型和树型。坐标型动态规划通常用来处理涉及空间位置的问题，如公共汽车接乘客的问题，其中公交路线和乘客位置构成二维空间，司机需要规划最优路径以接尽可能多的乘客。 线性型动态规划的特点是状态表示为一维数组，比如最长上升子序列问题。最长上升子序列是指一个数列中连续递增的部分，给定一个序列，目标是找到其最长的上升子序列。动态规划解决此问题的关键是定义状态转移方程，初始状态L(1)为1，接着通过比较元素之间的关系，找到当前元素可以添加到哪些先前的子序列来延长序列长度，从而递推得到L(i)。 例如，对于序列A={5,2,8,6,3,6,9,7}，动态规划方法可以通过遍历每个元素，检查所有小于当前元素的前一个元素，找出最长递增子序列。递推公式表示为：L(i) = max{L(j) + 1}，其中j < i 且 aj < ai。通过这样的方式，逐步计算出整个序列的最长上升子序列长度。 总结来说，动态规划在"拦截导弹"问题和最长上升子序列问题中，都是通过构建和更新一个状态表，利用最优子结构（即子问题的最优解组合形成原问题的最优解）来求解复杂问题。这种方法在IT行业中被广泛应用，因为它能够有效地处理具有重叠子问题和最优子结构的问题，提高了解决这类问题的效率。