其他DP问题type
status
date
slug
summary
tags
category
icon
password
Property
区间 DP
区间动态规划：线性 DP 的一种，简称为「区间 DP」。以「区间长度」划分阶段，以两个坐标（区间的左、右端点）作为状态的维度。一个状态通常由被它包含且比它更小的区间状态转移而来。
区间 DP 的主要思想就是：先在小区间内得到最优解，再利用小区间的最优解合并，从而得到大区间的最优解，最终得到整个区间的最优解。
根据小区间向大区间转移情况的不同，常见的区间 DP 问题可以分为两种：
- 单个区间从中间向两侧更大区间转移的区间 DP 问题。比如从区间转移到更大区间
- 多个（大于等于 2 个）小区间转移到大区间的区间 DP 问题。比如从区间和区间转移到区间
第1种区间 DP 问题基本思路
从中间向两侧转移的区间 DP 问题的状态转移方程一般为：
- 其中 表示为：区间（即下标位置到下标位置上所有元素）上的最大价值。
cost表示为：从小区间转移到区间 的代价。
- 这里的
max/min取决于题目是求最大值还是求最小值。
从中间向两侧转移的区间 DP 问题的基本解题思路如下：
- 枚举区间的起点
- 枚举区间的终点
- 根据状态转移方程计算从小区间转移到更大区间后的最优值
第2种区间 DP 问题基本思路
多个（大于等于 2 个）小区间转移到大区间的区间 DP 问题的状态转移方程一般为：
- 其中状态 表示为：区间 （即下标位置 到下标位置 上所有元素）上的最大价值
- 表示为：将两个区间与中的元素合并为区间中的元素的代价
- 这里的
max/min取决于题目是求最大值还是求最小值。
多个小区间转移到大区间的区间 DP 问题的基本解题思路如下：
- 枚举区间长度
- 枚举区间的起点，根据区间起点和区间长度得出区间终点
- 枚举区间的分割点，根据状态转移方程计算合并区间后的最优值
最长回文子串
题目：给一个字符串
s，找到s中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。示例：
对于一个子串而言，如果它是回文串，并且长度大于 222，那么将它首尾的两个字母去除之后，它仍然是个回文串。如对于字符串
“ababa”，如果已经知道“bab” 是回文串，那么 “ababa”一定是回文串，这是因为它的首尾两个字母都是 “a”。用
P(i,j)表示字符串 的第到个字母组成的串（表示成 s[i:j]）是否为回文串：可以写出动态规划的状态转移方程：
也就是说，只有
s[i+1:j-1] 是回文串，并且的第和个字母相同时，s[i:j]才会是回文串。边界条件：
树形 DP
树形 DP：在树形结构上实现的动态规划方法叫做树形 DP。树形 DP 的求解过程一般以节点从深到浅（子树从小到大）的顺序作为动态规划的「阶段」。将节点编号作为状态的第 1 维，代表以该节点为根的子树。
通常采用递归的方式求解每棵子树，在回溯时从子节点向上进行状态转移。在当前节点的所有子树求解完毕之后，才可以求解当前节点。
打家劫舍 III
题目：小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，称之为
root 。除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。给定二叉树的
root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。示例：
可以用 表示选择 节点的情况下， 节点的子树上被选择的节点的最大权值和； 表示不选择节点的情况下， 节点的子树上被选择的节点的最大权值和；和代表的左右孩子。
- 当被选中时，的左右孩子都不能被选中，故被选中情况下子树上被选中点的最大权值和为 和 不被选中的最大权值和相加，即
- 当不被选中时， 的左右孩子可以被选中，也可以不被选中。对于的某个具体的孩子，它对的贡献是被选中和不被选中情况下权值和的较大值。故
至此，可以用哈希表来存和的函数值，用深度优先搜索的办法后序遍历这棵二叉树，就可以得到每一个节点的和。根节点的 和的最大值就是要找的答案。
状态压缩 DP
状态压缩 DP：如果使用动态规划方法设计的状态是一个大小不超过
n的集合，并且集合中的每个元素都是小于k的正整数，则可以把这个集合看做是一个n位的k进制数，以一个 之间的十进制整数的形式作为动态规划状态的一维。这种把集合转化为整数记录在动态规划状态中的一类方法，被称为状态压缩动态规划方法。计数类 DP
计数类 DP：统计可行方案数的一类动态规划，区别于求解最优解，计数类 DP需要统计所有满足条件的可行解数量，这些问题需要满足不重复、不遗漏的条件。
不同路径 II
题目：一个机器人位于一个
mxn网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。示例：
不同的二叉搜索树
题目：给一个整数
n，求恰由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。示例：
假设个节点存在二叉排序树的个数是 ，令 为以为根的二叉搜索树的个数，则：
当 为根节点时，其左子树节点个数为 个，右子树节点为，则
综合两个公式可以得到 卡特兰数 公式
数位 DP
数位 DP：与数位相关的一类计数类动态规划，即在数位上进行动态规划。这里的数位指的是个位、十位、百位、千位等。
数位 DP 一般用来统计区间
[l, r] 上满足特定条件的元素个数，或者用于求解满足特定条件的第 k 小数。概率 DP
概率 DP：与概率相关的一类动态规划。由于概率和期望具有线性性质，使得可以在概率和期望之间建立一定的递推关系，从而通过动态规划的方式来解决一些概率问题。