leetcode 第 422 场算法比赛（差分DP）

零、背景

昨晚英雄联盟总决赛值班到两三点，睡得比较晚，今天打比赛时头昏沉沉的。

因此这次没状态，第二题和第三题都敲了半天，还WA一次。
第四题一开始DP想错了，想到正确的DP后发现空间很大爆栈了，随后比赛结束了。
吃完饭又看了最后一题，发现可以使用差分来优化空间，从而可以通过第四题。

A: 统计。
B: BFS + 优先队列。
C: BFS + 优先队列（与B题没区别）。
D: 差分DP。

排名：236
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/4/422

一、检查平衡字符串

题意：问数字奇偶位数字分别相加，是否相等。

思路：按题意循环相加，判断即可。
复杂度：O(n)

二、到达最后一个房间的最少时间 I

题意：给一个矩阵，从左上角走到右下角，每走一步消耗1秒时间。
每个位置有一个最早进入时间，问最少什么时候到达右下角。

思路: BFS 搜索。
如果下个位置时间没到，则最早到达时间是允许进入时间加1。

优化：同一个节点为了避免重复搜索，可以使用优先队列优化。
复杂度：O(n^2)

三、到达最后一个房间的最少时间 II

题意：给一个矩阵，从左上角走到右下角，奇数步消耗1秒，偶数步消耗2秒。
每个位置有一个最早进入时间，问最少什么时候到达右下角。

思路：BFS 搜索。

对于矩阵，每一个位置的步数的奇偶性是固定的，故根据坐标即可计算出加1还是加2.
除了加1与加2的不同，其他的其实与第二题没区别。

复杂度：O(n^2)

四、统计平衡排列的数目

题意：给一个数组，问存在多少个排列，使得奇偶位数字之和相等。

思路：差分DP。

由于是求所有排列，所以需要先统计[0-9]所有数字出现的次数。

朴素的思路：

状态定义：f(v,sum1,sum2,n1,n2)
含义：v 之后数字已经选择，奇数位选择 n1个，和为 sum1，偶数为选择 n2个，和为sum2 时，前 v 个数字可以得到的最优答案。

状态转移方程：

f(v,sum1,sum2,n1,n2) =
   C(nv1, i) 
 * C(nv2, j) 
 * f(v-1,sum1+i*v,sum2+j*v,n1+i,n2+j)

方程解释：数字 v 有 nv 个，枚举奇数选择 i 个，偶数则选择 j 个时的排列数。
由于奇数已经选择了 n1 个，所以剩余 nv1 个位置，选择 i 个的方案数是 C(nv1, i)。
同理，偶数的方案数是 C(nv2, j)。
剩余的递归即可。

空间复杂度：O(10 * 360 * 360 * 40 * 40)
空间复杂度差不多是 72000 * 72000，显然储存不下。

优化1：差分DP

分析 sum1 与 sum2 关系，当 v 固定时， sum1 与 sum2 的和是固定的。
同理，n1 和 n2 的和也是固定的。

故可以通过储存 sum1-sum2 以及 n1-n2 来压缩状态。
由于有负数，整体进行偏移即可。

状态：f(v, sum12, n12)
状态状态方程与上面的一样。
复杂度：O(10 * 720 * 80)

优化2：对半DP。

与差分 DP 类似，不过不需要储存差分状态，储存一半的状态，例如只储存奇数的状态。

状态定义：f(v, sum1, n1)
根据奇数的状态，推导出偶数的状态，状态转移方程与朴素的状态转移方程一样。
复杂度：O(10 * 360 * 40)

五、最后

这次比赛最后一题动态规划很经典，所有状态储存不下，但是部分状态之间存在约束关系，通过其中一个可以推导出另外一个，这时候只需要储存一个状态即可。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code