2 ms·
You could also solve it analytically with dynamic programming, computing the probability of falling for each spot on the plank.
by a1k0n 15y ago
You could also solve it analytically with dynamic programming, computing the probability of falling for each spot on the plank.
- scythe 15y agoWell, since you can walk back and forth across rows, you'll have to compute all of the probabilities for a given row at once by solving the resulting system of equations. This is generally quite simple. For example, take a four-column, one-row version, with probability-of-falling like so: * 0 0 0 0 * 1 x y y x 1 We have: x = 0 / 4 + 1 / 4 + y / 4 + x / 4 y = 0 / 4 + x / 4 + y / 4 + y / 4 giving the solutions x = 2/5 and y = 1/5. It is easier, of course, if you exploit the symmetry of the situation, as here (by writing x y y x instead of x y z w).