No.1 数组串联

解题思路

一个 for 循环解决。

代码展示

No.2 长度为 3 的不同回文子序列

解题思路

最多有 26 * 26 种长度为 3 的回文子序列，依次判断每一种子序列是否存在即可。

代码展示

No.3 用三种不同颜色为网格涂色

解题思路

状压 DP，将每一列压缩成一个 0 ~ 242 之间的数字即可（相当于 3 进制的表示）。

定义状态 dp[i][j] 表示第 i 列的涂色情况为 j 时，前 i 列的方案数。

状态转移 dp[i][j] = SUM(dp[i - 1][k]) if valid(j) and valid(k) and valid(j, k)

方程中 valid(j) 表示 j 本身是一个合法的涂色（一列中没有相邻的相同颜色），valid(j, k) 表示涂色 j 和 k 作为相邻的列时合法。

代码展示

No.4 合并多棵二叉搜索树

解题思路

DFS 即可，详见注释。

代码展示