期望\(DP\) 方法总结

这个题目太大了，变化也层出不穷，这里只是我的一点心得，不定期更新！

1. 递推式问题

对于无穷进行的操作期望步数问题，一般可用递推式解决。

对于一个问题\(ans[x]\)，

我们可以考虑建立逻辑转移：

\[ans[now] = Merge(\ \ Function(ans[now])\ ,\ Function(ans[other])\ \ )\]

那么我们进行移项后，

\[ans[now]\ Delete\ Function(ans[now])\ \ =\ \ Function(ans[other])\]

此时，分离了\(ans[now]\) 与\(ans[other]\)， 那么就构成了递推关系。

.

然后，对于递推式，巧用 顺序枚举 与 倒序枚举， 来防止除0、溢出等问题。

比较经典的就是POJ 2096 Collecting Bugs，它的原递推式：

\(f[i][j]*(sn-ij) = Function(f[i-1][j]\ ,\ f[i][j-1]\ ,\ f[i-1][j-1])\)

我们目标状态为\(f[s][n]\)，那么当\(i=s\)，\(j=n\)时就会出现除0的情况。

一个比较巧妙的处理，改变状态含义，把它变为倒序处理：

\(f[i][j]*(ns-ij) = Function(f[i+1][j]\ ,\ f[i][j+1]\ ,\ f[i+1][j+1])\)

然后\(f[s][n]=0\)，目标状态变为\(f[0][0]\)从而避免了除0的问题。

.

例题： 、。

2. 错位相减

注意式子的特性，观察特定情况下是否可以直接算或者错位相减。

注意式子的次数是否等差，当下表值达到一定程度时是否存在特殊计算方法。

例如：

\(f[i]=f[i-1]p_b+p_a(f[i-1]+1)p_b+{p_a}^2(f[i-1]+2)p_b+....\)

那么有\(p_af[i] = p_afp_b + {p_a}^2(f[i-1]+1)p_b + {p_a}^3(f[i-1]+2)p_b+...\)

然后错位相减可得：

\((1-p_a)f[i] = p_b(f[i-1] + p_a + {p_a}^2 + {p_a}^3 + ....)\)

此时出现了等比数列，套等比数列求和即可。

一般错位相减后 各种数学公式套一波 就可以把无限变为有限 。

例题：

3. 高斯消元

这个真的是套路了，大家应该都会。

对于一个\(DP\)方程式，

若所有的转移方程式都形如\(f(x) = Function_{i=1}^n f(i)\)

那么直接移项，然后把每一个转移方程式当作一个方程，高斯消元即可。

例题： ，

4. 步骤移动转移

当直接用所需状态设不出方程式的时候，考虑从当前状态移动一步的条件与概率

那么状态变为\(f[移动步数]\)，

转移为\(f[step] ==(Function)==> f[step+1]\)

以这个角度思考，很有可能会出现递推式，然后套用上面所说就可解出最终答案。

例题：。

5. 整数期望公式

我们设答案(整数)为\(x\)，期望答案为\(E(x)\) ，\(P(x \ge i)\)表示答案大于等于\(i\)的概率，那么有：

\[E(x) = \sum_{i = 1}^∞ P(x \ge i)\]

我们同时有：\(P(i \leq x-1) + P(i \ge x) = 1\)

第一个公式中的无限看起来很吓人，但根据实际意义可以变为有限(答案不可能大于最大上限)。

用这个公式可以将求解答案变为求解后缀和或者求解前缀和。

那么就改变了\(DP\)目标，有时候就可以帮助我们设计出可以转移的状态,最后套公式得解即可。

例题： (难度较大强行插入大佬的题解：、)