前排广告：
字节跳动垂直业务，base北京，求后端实习、校招（10月开始）、社招，看我动态部门直推，谢谢大家 😭。
字节跳动垂直业务，base北京，求后端实习、校招（10月开始）、社招，看我动态部门直推，谢谢大家 😭。
假设有两个数组 a 和 b，a 和 b 没有共同的元素，且 a 并上 b 为 1~n 的一个排列。
现在想要 merge(a, b) ，merge 规则如下：
如果 a1 < b1，则 merge(a, b) = [a1] + merge([a2...an], b)
如果 a1 > b1，则 merge(a, b) = [b1] + merge(a, [b2...bn])
举个例子 a=[3,1] b=[2,4]
3<2，所以第一位是 2，
3<4，所以第二位是 3，
1<4，所以第三位是 1，
第四位是 4。
即 merge 的结果是 [2, 3, 1, 4]
问题：
给出 merge 后的数组（长度为 2n），问能否找到两个长度相对的数组，可以进行 merge 得到该数组。（只需要输出 YES 或 NO）
解：
首先注意到 n <= 2000，可以知道是个 n*n 的 DP。
然后考虑怎么定义这个 DP 数组，才能维护这个状态。
一开始考虑 dp[i][j][k] 表示到第 i 个数时，最大的数在数组 j (0 <= j <= 1，即要么在数组0，要么在数组1)，最大的数是 k 时是否存在方案。
首先这样状态表述不完整，无法推导出最终的答案，即没办法保证最后两个数组的长度相等。
然后可以发现最大的数不需要记录，一定是前缀最大值，这个可以预处理出来。
然后我们可以维护下数组 j 的长度，所以 dp[i][j][k] 表示到第 i 个数时，最大的数在数组 j，数组 j 长度是 k 时是否存在方案。（0 <= dp[i][j][k] <= 1）
假设我们要构造的数组是 a 和 b 两个数组，a 已经构造了前 an 个数，b 已经构造了 bn 个数，假设此时出现的最大的数是 X，那么当我们拿到 num[i] 的时候，有两种情况：
（假设 j 此时是 a ）
（1）num[i] > X
这个时候 num[i] 既可以放到 a 的后面（dp[i][j][k+1] = 1），也可以放到 b 的后面（dp[i][!j][i-k] = 1）
（2）num[i] < X
这个时候只能放到 a 的后面（dp[i][j][k+1] = 1）
（考虑如果不放到 a 的后面会有什么问题，可以尝试模拟下看看）
最终 dp[2*n][0][n] == 1 或 dp[2*n][1][n] == 1 则说明存在方案。
从零开始的一百道DP题持续更新😭
全部评论
(0) 回帖