线性、区间、树形 DP

原文oi wiki:树形 DP区间 DP

1. 线性 DP

每个状态只依赖于前一个或前几个状态，且状态转移是线性的（即没有复杂的依赖关系）。通常用于解决序列或数组上的问题。

启发式算法是什么呢？ 启发式算法是基于人类的经验和直观感觉，对一些算法的优化。 说白了,用思维去强行干碎(不是)复杂度

树上启发式合并

原文oi wiki:dsu-on-tree 我们考虑树上的离线问题或者是其他情况可以从树上dp的角度去思考：

例题

例题1 例题2

原文oi wiki:LIS

简单情形

在最长上升子序列问题中，我们引入两个关键变量 i 和 j。这里，i 表示以其作为结尾的最长上升子序列的长度，而 j 则作为连接点，在构建最长上升子序列的过程中起着重要作用。

需要特别注意的是，dp[mx] 并不一定就是最终答案。在得出所有以不同元素结尾的最长上升子序列长度后，我们需要遍历整个结果数组，才能找出真正的最长上升子序列长度。