CSP 线性动态规划入门

dp部分一：线性动态规划算法

知识概述

动态规划算法（简称为dp）在算法设计中占据着关键地位，通常应用于寻找全局最优解或统计相关数量的情形。将动态规划算法的学习过程与贪心算法的学习进行比较，可以发现两者的相似之处，但二者的目标存在差异。贪心算法旨在获取局部最优解，在执行求解的过程中仅能确保所得结果满足当前已知的约束条件。对于某些复杂的题目，采用贪心算法可能会得到多个不同的局部最优解，难以辨别哪个才是真正的全局最优解。而动态规划问题则通过递推的方式逐步求得全局最优解，其核心思想在于全局最优解必然包含其子问题的最优解。针对需要解决的问题，通过多步骤的简化和分解，最终将其转化为一个递推表达式。

在充分理解动态规划的本质后可以发现，这种算法并非一种具体的、明确的计算方法，而是类似于贪心或分治策略的一种思维方式。依据“最优解包含最优子解”的原理可以得出逻辑推论：在求取某个最优解时，只有之前计算出的结果会对当前结果产生影响，而后续计算的结果则不会产生影响。借助这一结论，新的解可以表示为多个已知结果的递推关系式。在整个求解过程中，每一步都基于已知量采取了最优化策略，从而确保每个阶段所得到的都是局部最优的解决方案，并最终实现对全局最优解的获取。

综上所述，在处理动态规划问题时有两个方面尤为关键：初始状态和状态转移递推关系式。在解决一个具体的动态规划问