### Fype's blog

By Fype, 15 months ago,

It's one of the most beautiful dp I ever used. I'm going to explain it with an example.

Problem: 1265E

Solution: suppose $e_i$ equals the expected number of days that we stop.
$e_i = p_i * e_{i + 1} + (1 - p_i) * e_1 + 1$
$e_n = (1 - p_i) * e_1 + 1$

So how to update $e$?! :D
We will change how we show numbers. You know how we show complex numbers (if you don't learn it here), we are going to use the same idea.
Each number consists a part that is $e_1$ and another part that is a Real number(in this problem you can change it to integer when using modulo).
We show each number with $x$ and $y$ such that the number is equal to $x * e_1 + y$. So we use this idea and start updating $e$ backward.
Then we will get $e_1 = x * e_1 + y$ and now we can get $e_1$ as an intiger.
$e_1 = y / (1 - x)$

Any other problem that uses the same idea, please mention. :D

• +100