DP问题不完全总结.pdf

动态规划（DP）是一种强大的算法思想，用于解决最优化问题，通过将复杂问题分解成更小的子问题来求解。以下是对DP问题不完全总结的详细解释： 1. 编号(长度)动态规划： 这类问题的核心在于状态通常由序列的长度或位置编号来定义。例如： - 最长不下降子序列：状态(i)表示考虑前i个元素时的最长不下降子序列。通过单调栈或单调队列，可以将时间复杂度优化到O(nlogn)。 - LCS (最长公共子序列)：状态(i, j)表示两个字符串第i和第j位置对应的最长公共子序列。这类问题可以通过二维数组存储状态，进行递推计算。 2. 区间动态规划： 这类问题涉及到区间内的决策，往往与分割或覆盖问题相关。例如： - 邮局选址问题：状态表示第k个邮局可以覆盖的村庄范围。通过区间决策，可以找到最优的邮局布局，降低转移时间至O(1)。 - 石子合并游戏：涉及到区间合并的操作，通过动态规划可以找到最佳策略。 3. 坐标动态规划： 这类问题的状态包括坐标和其他维度，常与二维或高维划分问题相交叉。例如： - 棋盘分割：状态由棋盘的两个对角坐标定义，通过变换公式，可以构造动态规划方程来求解。 4. 数轴动态规划： 这类问题发生在一维数轴上，如01背包问题： - 01背包：状态表示在容量限制下，选择部分物品的最大价值。可以使用动态规划求解，通过添加last属性来优化空间复杂度。 - 取火柴问题：玩家轮流取火柴，最后取走最后一根火柴的人获胜，动态规划可以找出最优策略。 5. 树型动态规划： 这类问题涉及树结构，通常采用后序遍历顺序，将多叉树转化为二叉树以简化问题： - 动态规划在树上的应用：比如在树上寻找最短路径、最大路径等问题，需要考虑子节点对当前节点的影响。 动态规划的关键在于定义合适的状态和状态转移方程，以及有效地利用子问题的解决方案。通过巧妙地设计状态，可以避免重复计算，提高效率。在实际应用中，还需要结合其他算法技术，如贪心、分治等，以解决更复杂的问题。