算法-动态规划(三)

概述

本文主要介绍线性 DP 中的最长上升子序列模型，与该模型相关的题目有：最长上升子序列、登山、友好城市、最大上升子序列和。

最长上升子序列

题目描述及示例

给定一个长度为 $N$ 的数列，求数值严格单调递增的子序列长度最长是多少?

Input:
// 第一行包含整数N。
7
// 第二行包含N个整数，表示完整序列。
3 1 2 1 8 5 6
    
Output:
// 输出一个整数，表示最大长度。
4

解题思路

• 数据存储

  nums[i] 用于存储完整序列。

• 状态表示

  既然数据是一维的，状态表示大概率也是一维的。我们可以这样定义 $f[i]$：以 $nums[i]$ 为结尾、数值严格单调递增的所有子序列中最长的序列长度。

• 状态转移

  子序列要求数值严格单调递增，故而 $f[i]$ 可由那些位于 $num[i]$ 前方、数值小于 $num[i]$ 的 $f[k]$ 转移得到，故而状态转移方程可表示如下：

  $$f[i] = max(f[k] + 1,f[i]),(0\leq k < i \ 且 \ nums[k] < nums[i])$$

• 状态初始化

  对于此题目而言，状态初始化比较复杂，需要指定 $f[i] = 1,(0 \leq i < nums.length)$ 。

登山

题目描述及示例

五一到了，ACM 队组织大家去登山观光，队员们发现山上一个有 $N$ 个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

Input:
// 第一行包含整数N，表示景点数量。
8
// 第二行包含N个整数，表示每个景点的海拔。
186 186 150 200 160 130 197 220
    
Output:
// 输出一个整数，表示最多能浏览的景点数。
4

解题思路

• 数据存储

  nums[i] 用于存储景点海拔序列。

• 状态表示

  我们先对题意作一简单分析：队员所浏览景点海拔可看做先单调上升后单调下降的曲线，那么我们可首先求得从前往后到任意点的最长单调上升子序列长度，随后求取从后往前到任意点的最长单调上升子序列长度，统计各点作为最高点时的曲线长度，最长者便是最多可浏览的景点数。

  这里我们需要定义两个状态 $f[i]$：以 $nums[i]$ 为结尾、数值严格单调递增的所有子序列中最长的序列长度， 和 $g[i]$：以 $nums[i]$ 为起始，数值严格单调递减的所有子序列中最长的序列长度。

• 状态转移

  状态转移基本与 最长上升子序列 相同，两者的状态转移方程可表示如下：

  $$f[i] = max(f[k] + 1,f[i]),(0\leq k < i \ 且 \ nums[k] < nums[i])$$

  $$g[i] = max(g[k] + 1, g[i]),(i < k < nums.length \ 且 \ nums[k] < nums[i])$$

• 状态初始化

  状态初始化也基本与 最长上升子序列 相同，需要指定 $f[i] = g[i] = 1,(0 \leq i < nums.length)$ 。

友好城市

题目描述及示例

Palmia 国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的 $N$ 个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

Input:
// 第一行包含整数N，表示城市数。
7
// 第二行到第n+1行，每行两个整数，分别表示南岸和北岸的一对友好城市的坐标。
22 4
2 6
10 3
15 12
9 8
17 17
4 2
    
Output:
// 输出一个整数，表示政府所能批准的最多申请数。
4

解题思路

• 数据存储

  first[i] 存储北岸城市坐标，second[i] 用于存储与北岸对应的友好城市坐标。

• 状态表示

  如果两条航道发生交叉，一定满足如下条件：$(first[i] < first[j] \ 且 \ second[i] > second[j])$ 或 $(first[i] > first[j] \ 且 \ second[i] < second[j])$。如果我们对 $first[i]$ 从小到大进行排序，并根据排序结果调整各友好城市在 $second[j]$ 中的坐标位置，为使得航道之间不会发生交叉结果，我们就需要保证：所选择的友好城市坐标满足单调递增。那么这样就将该题转换为 最长上升子序列。所以我们可以这样定义 $f[i]$：以 $second[i]$ 为结尾、坐标位置严格单调递增的所有子序列中最长的序列长度。

• 状态转移

  状态转移基本与 最长上升子序列 相同，状态转移方程可表示如下：

  $$f[i] = max(f[k] + 1,f[i]),(0\leq k < i \ 且 \ second[k] < second[i])$$

• 状态初始化

  状态初始化也基本与 最长上升子序列 相同，需要指定 $f[i] = g[i] = 1,(0 \leq i < second.length)$ 。

最大上升子序列和

题目描述及示例

一个数的序列 $bi$，当 $b1<b2<…<bS$ 时，我们称这个序列是上升的。对于给定的一个序列 (a1,a2,…,aN)，我们可以得到一些上升的子序列 (ai1,ai2,…,aiK)，其中 $1≤i1<i2<…<iK≤N$。比如，对于序列 (1,7,3,5,9,4,8)，有它的一些上升子序列，如 (1,7),(3,4,8) 等。这些子序列中和最大为18，为子序列 (1,3,5,9) 的和。

你的任务，就是对于给定的序列，求出最大上升子序列和。注意：最长的上升子序列的和不一定是最大的，比如序列 (100,1,2,3) 的最大上升子序列和为 100，而最长上升子序列为 (1,2,3)。

Input:
// 第一行是序列长度N。
7
// 第二行给出序列中的N个整数
1 7 3 5 9 4 8
    
Output:
// 输出一个整数，表示最大上升子序列和。
18

解题思路

• 数据存储

  nums[i] 用于存储完整序列。

• 状态表示

  与 最长上升子序列 类似，我们可以这样定义状态 $f[i]$：以 $nums[i]$ 为结尾、数值严格单调递增的所有子序列中最大的序列和。$f[i]$ 中最大值即为最长上升子序列和。

• 状态转移

  状态转移基本与 最长上升子序列 相同，状态转移方程可表示如下：

  $$f[i] = max(f[k] + nums[i],f[i]),(0\leq k < i \ 且 \ nums[k] < nums[i])$$

• 状态初始化

  由于状态存储序列和，故而需要如此初始化：指定 $f[i] = nums[i],(0 \leq i < nums.length)$ 。