【算法提高：动态规划】1.2 最长上升子序列模型（TODO：最长公共上升子序列）

题目列表

1017. 怪盗基德的滑翔翼

https://www.acwing.com/problem/content/1019/

注意 基德 可以从任意地方开始选择向左或向右出发。
所以需要 dp 两次。

import java.io.BufferedInputStream;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));int k = sin.nextInt();while (k-- != 0) {int n = sin.nextInt(), ans = 1;int[] a = new int[n], dp = new int[n];Arrays.fill(dp, 1);for (int i = 0; i < n; ++i) {a[i] = sin.nextInt();for (int j = 0; j < i; ++j) {if (a[i] < a[j]) dp[i] = Math.max(dp[i], dp[j] + 1);}ans = Math.max(ans, dp[i]);}Arrays.fill(dp, 1);for (int i = n - 1; i >= 0; --i) {for (int j = n - 1; j > i; --j) {if (a[i] < a[j]) dp[i] = Math.max(dp[i], dp[j] + 1);}ans = Math.max(ans, dp[i]);}System.out.println(ans);}}
}

1014. 登山

https://www.acwing.com/problem/content/1016/

因为一旦开始向下走之后就不会再往上走了。

所以向上走的状态只能从向上走的状态转移过来；向下走的状态既能从向上走的状态转移过来，也可以从向下走的状态转移过来。

import java.io.BufferedInputStream;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));int n = sin.nextInt();int[] a = new int[n];for (int i = 0; i < n; ++i) a[i] = sin.nextInt();int[][] dp = new int[n][2];int ans = 1;for (int i = 0; i< n; ++i) {dp[i][0] = dp[i][1] = 1;for (int j = 0; j < i; ++j) {if (a[i] > a[j]) {dp[i][0] = Math.max(dp[i][0], dp[j][0] + 1);}else if (a[i] < a[j]) {dp[i][1] = Math.max(dp[i][1], Math.max(dp[j][0], dp[j][1]) + 1);}}ans = Math.max(ans, Math.max(dp[i][0], dp[i][1]));}System.out.println(ans);}
}

482. 合唱队形

https://www.acwing.com/problem/content/484/

计算每个节点作为结尾位置时向左和向右的递减子序列的最长长度即可。

注意最后要求的答案是需要几位同学出列 而不是 最多保留几位同学。

import java.io.BufferedInputStream;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));int n = sin.nextInt();int[] t = new int[n];for (int i = 0; i < n; ++i) t[i] = sin.nextInt();int[][] dp = new int[n][2];for (int i = 0; i < n; ++i) {dp[i][0] = dp[i][1] = 1;for (int j = 0; j < i; ++j) {if (t[i] > t[j]) dp[i][0] = Math.max(dp[i][0], dp[j][0] + 1);}}int ans = 1;for (int i = n - 1; i >= 0; --i) {for (int j = n - 1; j > i; --j) {if (t[i] > t[j]) dp[i][1] = Math.max(dp[i][1], dp[j][1] + 1);}ans = Math.max(ans, dp[i][0] + dp[i][1] - 1);}System.out.println(n - ans);}
}

1012. 友好城市（⭐排序后 最长上升子序列模型）

https://www.acwing.com/problem/content/1014/

按照一岸排序，求另一岸此时的最长递增子序列。

import java.io.BufferedInputStream;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));int n = sin.nextInt();int[][] a = new int[n][2];for (int i = 0; i < n; ++i) {a[i][0] = sin.nextInt();a[i][1] = sin.nextInt();}// 按照一岸排序Arrays.sort(a, (x, y) -> x[0] - y[0]);// 求另一岸此时的最长递增子序列int ans = 0;int[] dp = new int[n];Arrays.fill(dp, 1);for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {if (a[i][1] > a[j][1]) dp[i] = Math.max(dp[i], dp[j] + 1);}ans = Math.max(ans, dp[i]);}System.out.println(ans);}
}

1016. 最大上升子序列和

https://www.acwing.com/problem/content/1018/

跟最长上升子序列长度的方法差不多，只修改了递推公式部分，将 + 1 修改成了 + a[i]。

import java.io.BufferedInputStream;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));int n = sin.nextInt();int[] a = new int[n];for (int i = 0; i < n; ++i) a[i] = sin.nextInt();int[] dp = new int[n];Arrays.setAll(dp, i -> a[i]);int ans = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {if (a[i] > a[j]) {dp[i] = Math.max(dp[i], dp[j] + a[i]);}}ans = Math.max(ans, dp[i]);}System.out.println(ans);}
}

1010. 拦截导弹

https://www.acwing.com/problem/content/1012/

使用最长上升子序列模型解决问题1。（对于这题是个最长递减子序列）。

对于问题2，当一个新的导弹来临时，我们首先检查是否有已经存在的系统可以拦截它。如果可以，我们应该选择一个能够拦截这个新来的导弹并且当前最高高度最低的系统来拦截它。
结论：从上面的贪心可以推出来，是在求最长上升子序列。

解法1——最长递减子序列 + 贪心

import java.io.BufferedInputStream;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));final int N = 1001;int[] a = new int[N], dp = new int[N];int n = 0;while (sin.hasNext()) {a[n++] = sin.nextInt();}// 使用动态规划求解最多能拦截的导弹数int ans1 = 0;Arrays.fill(dp, 1);for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {if (a[i] <= a[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}ans1 = Math.max(ans1, dp[i]);}System.out.println(ans1);// 贪心List<Integer> ls = new ArrayList<>();for (int i = 0; i < n; ++i) {int k = 0;while (k < ls.size() && ls.get(k) < a[i]) k++;if (k >= ls.size()) ls.add(a[i]);else ls.set(k, a[i]);}System.out.println(ls.size());}
}

解法2——最长递减子序列 + 最长递增子序列（⭐贪心结论）

import java.io.BufferedInputStream;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));final int N = 1001;int[] a = new int[N], dp = new int[N], dp2 = new int[N];int n = 0;while (sin.hasNext()) {a[n++] = sin.nextInt();}// 不递增和递增子序列的最大长度int ans1 = 0, ans2 = 0;Arrays.fill(dp, 1);Arrays.fill(dp2, 1);for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {if (a[i] <= a[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);} else dp2[i] = Math.max(dp2[i], dp2[j] + 1);}ans1 = Math.max(ans1, dp[i]);ans2 = Math.max(ans2, dp2[i]);}System.out.println(ans1 + "\n" + ans2);}
}

187. 导弹防御系统⭐⭐⭐⭐⭐（至少需要多少个 上升/下降 子序列）（dfs + 最少需要多少最长上升子序列）⭐⭐⭐⭐⭐

https://www.acwing.com/problem/content/189/

注意数据范围是 50 比较小。

在上一题的代码框架基础上 增加一个 dfs 爆搜。

import java.io.BufferedInputStream;
import java.util.*;public class Main {final static int N = 52;static int[] q = new int[N], up = new int[N], down = new int[N];static int ans = 0, n = 0;public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));while (true) {n = sin.nextInt();if (n == 0) return;ans = 0;dfs(0, 0, 0);System.out.println(ans);}}// u,su,sd 表示枚举到了第一个数，当前上升子序列的个数，当前下降子序列的个数static void dfs(int u, int su, int sd) {if (su + sd >= ans) return;if (u == n) {ans = su + sd;return;}// 情况1：将当前数放到上升子序列中int k = 0;while (k < su && up[k] >= q[u]) k++;int t = up[k];up[k] = q[u];if (k < su) dfs(u + 1, su, sd);else dfs(u + 1, su + 1, sd);up[k] = t;      // 恢复现场// 情况2：将当签署放到下降子序列中k = 0;while (k < sd && down[k] <= q[u]) k++;t = down[k];down[k] = q[u];if (k < sd) dfs(u + 1, su, sd);else dfs(u + 1, su, sd + 1);down[k] = t;}
}

Q：为什么不用 bfs 来求解？
A：因为 bfs 需要的空间太大，可能会爆炸。（bfs 存一层，dfs 存一个路径）。

272. 最长公共上升子序列⭐⭐⭐⭐⭐

https://www.acwing.com/problem/content/274/

解法1——一起计算🚹TODO

dp[i][j] 表示 两个数组 0 ~ i 和 0 ~ j 之间的 且以 b[j] 为结尾的 最长公共上升子序列长度。

import java.io.BufferedInputStream;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));int n = sin.nextInt();int[] a = new int[n], b = new int[n];for (int i = 0; i < n; ++i) a[i] = sin.nextInt();for (int i = 0; i < n; ++i) b[i] = sin.nextInt();// dp[i][j] 表示 两个数组 0 ~ i 和 0 ~ j 之间的最长公共上升子序列长度。int[][] dp = new int[n + 1][n + 1];for (int i = 1; i <= n; ++i) {int maxV = 1;      // 可以上升的长度for (int j = 1; j <= n; ++j) {dp[i][j] = dp[i - 1][j];if (a[i - 1] == b[j - 1]) dp[i][j] = Math.max(dp[i][j], maxV);  	// 相等，是公共子序列if (b[j - 1] < a[i - 1]) maxV = Math.max(maxV, dp[i - 1][j] + 1);	// 更新可以上升的长度}}int ans = Arrays.stream(dp[n]).max().getAsInt();System.out.println(ans);}
}

解法2——先求最长公共子序列，再求最长上升子序列长度🚹TODO

在这里插入代码片

相关链接

【算法】最长递增子序列：动态规划&贪心+二分查找