# Go to the Problem

It’s easy since I spent only 2+ hours. So try it before read my thought and you’ll have some fun.

I study Ping-Cheng Yeh’s probability course on Coursera recently and want to try some puzzle on project euler, so I pick up this one.

• Try to compute the probability from the first to the last croak is difficult since there are many overlapped sub-trees.
• So try to solve it from the last croak. It turns out can be solved with dynamic programming.
• CROAKS[-1] is ‘N’, we known the chance the frog would croak a ‘N’ in every square.
• CROAKS[-2] is ‘P’, we known the probability to get CROAKS[-2:] in position X is P(CROAKS[−2] in X)⋅0.5⋅(P(CROAKS[−1] in X - 1)+P(CROAKS[−1] in X + 1))P(CROAKS[−2] in X)⋅0.5⋅(P(CROAKS[−1] in X - 1)+P(CROAKS[−1] in X + 1))
• Keep solving the last problems to get final ones.
• Sum the final probabilities give the answer.