13.1
大概思路是 +
具体请根据160页、161页两个数组的定义将思路写成算法形式。
13.2
- 设
表示前i个自然数构成的集合是否存在元素和是j - 状态初始化
，若 ，若
- 状态转移方程
，若 ，若
- 时间复杂度
13.4
- d[i]表示以第i个数结尾的最长非减序列的长度
- d[1]=1
- 状态转移方程
- 复杂度
13.5
- 设问题
表示前 个数字划分为 份的最低代价 - 目标问题是解决
- 线性代价先求出
的前 项和 - 初始状态
- 状态转移方程为是
表示的是在第 个切最后一刀划分的情况。 - 时间复杂度为
，空间复杂度为
下面再给出一些改进的思路 +
13.8
(1)
- 以
表示x中前i个构成的串，和y中前j个构成的串的最长公共子序列 - 则
，若 ，若 ，若
(2)
- 以
表示x中前i个构成的串，和y中前j个构成的串的最长公共子序列 - 则
，若 ，若 ，若
(3)
- 以
表示x中前i个构成的串，和y中前j个构成的串的最长公共子序列 - 以
表示最长公共子序列对应的 将来还能使用的次数。 - 则
，若 ，若 ，若
- 则
，若 ，若 ，若 ，若
13.9
- 设
表示以 结尾和以 开头的两个最长连续子串，且 - 则
，若 ，若
- 计算
的代价是 ，同时结果还需 开销来遍历 取最大值 - 总的复杂度是平方级别
13.10
- 设
表示 和 的最短公共超序列 - 则
，若 ，若 ，若 ，若 ，若
13.11
(1)
不对，例如
(2)
- 设
为 中前i个数和 中前j个数能否合成为 中前i+j个数 - 复杂度
(3)
- 设
为 中前i个数和 中前j个数合成为 中前k个数需要删除的元素集合。 是下面几种可能的情况中最小的集合 ，若 ，若
- 复杂度
13.12
(1)
- 设
表示前i个字符的子串是否合法 - 复杂度
(2)
第一问的
13.13
(1)
表示原串 表示以第 个字符结尾的长度为 的子串对应的最长回文子序列长度 - 若
，则 - 若
，则 - 这里为什么要这样假设
？如果认为 表示子串 的最长回文子序列长度，有什么不好的地方？
(2)
- 本题和13.12的第一问几乎一个思路。
- 首先对于给定的一个子串str[i...j]，需要判断是不是回文串check[p,q]，其中p=j，q=j-i+1，表示以第p个字符结尾的长度为q的子串是否为回文串。
- check的功能对应到13.12的dict()函数
- 回文串的判断本身可以用dp来做，
的复杂度。 - 若
，则 - 若
，则 - 否则
- 若
- 设
表示以第i个字符结尾的子串最少拆分回文数
13.15
本题只考虑
(2)
表示用面值 的硬币能否兑换j - 复杂度O(nv)
(3)
表示用面值 的硬币能否兑换j，且要求使用不超过t个硬币 - 复杂度O(nvk)
13.16
- 设
表示第i个节点所在子树的最小点覆盖数，且要求节点i在点覆盖集中 - 设
表示第i个节点所在子树的最小点覆盖数，且要求节点i不在点覆盖集中 - 则状态转移方程
- 转移顺序是从叶子节点向根节点转移
- 复杂度是线性，因为每个节点在做一次根节点和做一次子节点时访问到，O(2n)
13.18
- 假设
表示到达第i个旅店的最小惩罚 - 则
- 通过
的代价获得到每个旅店的最小惩罚 - 在更新
的状态转移矩阵的时候可以记录每个旅店最小惩罚对应的前一个旅店位置
13.23
- 本题是树的dp，思路和13.16几乎一样，设友好度评价为
- 设
表示第i个节点所在子树的最大评价，且要求节点i在名单中 - 设
表示第i个节点所在子树的最大评价，且要求节点i不在名单中 - 则状态转移方程
- 转移顺序是从叶子节点向根节点转移
- 复杂度是线性，因为每个节点在做一次根节点和做一次子节点时访问到，O(2n)
13.24
- 换个角度思考，题目等价于把比萨店进行划分，使得两条路线的和最小（想象是两个骑手）。
- 假设
是对前i个店进行划分后的最短路程，i>j，并且第一个骑手以i店结尾，第二个骑手以j店结尾。 - 显然第j+1到第i个店都是属于第一个骑手的。
- 初始情况，
- 假设已知
,则状态转移方程如下 - 上述状态转移方程本质上讨论的是比萨店
分配给哪个骑手。 - 复杂度
