最优解问题

动态规划 Dynamic Programming，DP

动态规划是一种将复杂问题分解为多个子问题来解决的算法方法，适用于存在重叠子问题和最优子结构的情况

通过将子问题的解存储起来（通常使用数组或表格），避免重复计算子问题，从而提高效率

1、定义状态：通过定义状态来描述问题的局部解，通常使用一个数组或表来存储这些状态。

2、状态转移方程：通过状态转移方程将问题分解为子问题。

3、初始状态和边界条件：为递推提供初始解和边界条件。

4、求解：通过迭代或递归求解状态，最终得到全局最优解。

贪心算法是每一步都选择当前局部看来最优的解，期望通过局部最优解推导出全局最优。贪心算法要求额外难题具备贪心选择性质和最优子结构

是一种通过尝试所有可能的解，逐步构建解并在发现当前解不可行时回退的算法，适用于组合优化问题，但由于其遍历所有可能解，时间复杂度通常较高

分治法将问题分解为多个规模更小的子问题，分别求解这些子问题，然后将解合并以获得全局最优解

分支限界是一种通过构建解空间树来搜索解的算法，通过估算和限制来剪枝不可能的解，以减少搜索空间，它与回溯算法类似，但分支限界使用了估算函数来限制解的探索。

启发式算法是一种基于经验规则的近似算法，通过试探性的方式搜索可能解，并通过启发函数来引导搜索过程。

遗传算法是一种基于自然选择和遗传学的启发式搜索算法。它通过选择、交叉、变异等操作生成一代代候选解，逐步逼近全局最优解。

模拟退火是一种全局优化算法，灵感来源于物理学中的退火过程。它通过引入随机性和温度变量来避免陷入局部最优，最终逐步收敛到全局最优解。