状态值$f_x = \sum \limits_{y \in x} p_y f_y$，$y$为$x$的子状态，$p_y$是对应的概率

eg:

链接：https://www.nowcoder.com/questionTerminal/b5c4d567ca6a450eae7bee2852078b10?toCommentId=20052476&ran=927 来源：牛客网

小欧拿了n个杯子排成了一排，其中有k个杯子装满了水，剩余的n−k个杯子为空的。小欧每回合的操作如下：

1. 随机选择一个杯子。
2. 杯子是空的。回合直接结束。
3. 杯子是满的。如果小欧上一回合喝过了水，则回合结束；否则将喝完这杯水，回合结束。

小欧想知道，她喝完所有水的回合数期望是多少？

$\left \{ \begin{array}{ccl} f_{n,k,0} & = & \frac{k}{n} (f_{n,k-1,1}+1)+\frac{n-k}{n}(f_{n,k,0}+1)\\ f_{n,k,1} & = & f_{n,k,0}+1 \end{array} \right. \Rightarrow f_{n,k,0}=\frac{n}{k}+f_{n,k-1,1}$

$f_{n,1,0} = n + f_{n,0,1} = n$

$f_{n,k,0} = \frac{n+k}{k} + \frac{n+k-1}{k-1} + \cdots + \frac{n+2}{2} + n$