Viterbi algorithm is a dynamic programming algorithm for finding the most probable sequence of hidden states given a sequence of observations in an HMM.
The table in your solution has one row per hidden state (O, F, B) and one column per observation ($\emptyset$, head, head) where $\emptyset$ denotes the beginning of the observation sequence. So, the first column tells you with what probabilities we start from each state. Since we always start from O and never from the other states, the first columns is 1, 0, 0.
The second column says, given the probabilities in the previous (i.e. the first) column, what is the probability that we end up at each state after observing the first observation. It seems that the probability of going form state O to F and B is the same and equal to $0.5$. So, your first graph should be like this:
1. After the first observation
Keep in mind that we know that in the beginning we were in state O with probability 1.
Probability of staying at O is 0.
Probability of going to F (from O) is $0.5$ and probability of observing a head (the first observation) there is $0.5$, so, probability of ending up at F after the first observation is $1 \times 0.5 \times 0.5 = 0.25$.
Probability of going to B (from O) is $0.5$ and probability of observing a head (the first observation) there is $0.9$, so, probability of ending up at B after the first observation is $1 \times 0.5 \times 0.9 = 0.45$.
2. After the second observation
The probability of ending up at O, F, or B after the second observation (head) is as follows:
2.1. Probability of ending up at O:
... is zero since there is no way we can enter O (see the diagram).
2.2. Probability of ending up at F:
... there are 3 possibilities:
- assuming we came from O: has probability 0 (see 2nd column of your table)
- assuming we came from F: has probability $0.25 \times 0.9 \times 0.5 = 0.1125$
- assuming we came from B: has probability $0.45 \times 0.9 \times 0.5 = 0.2025$
The most probable hypothesis is that we have come form state B.
2.3. Probability of ending up at B:
... there are 3 possibilities:
- assuming we came from O: has probability 0 (see 2nd column of your table)
- assuming we came from F: has probability $0.25 \times 0.1 \times 0.9 = 0.0225$
- assuming we came from B: has probability $0.45 \times 0.1 \times 0.9 = 0.0405$
The most probable hypothesis is that we have come form state B.
3. The Viterbi solution
According to the 3rd column of your table, the most probably hypothesis is that after observing two heads with this HMM we end up in state F (it has probability $0.2025$ versus $0.0405$ for state B and $0$ for state O). According to section 2.2, most likely, we have come from $B$ and we know that we started form O (these are indicated by arrows in your table). So, the Viterbi state sequence is O, B, S.
