Based on the official tutorial.

If we let \(dp[0][0] = dp[0][1] = 1\), then the transform will be:

If \(s_i\) = 0,

• \(dp[i][0] = dp[i - 1][0] + (dp[i - 1][1])\)
• \(dp[i][1] = dp[i - 1][1]\)

if \(s_i\) = 1,

• \(dp[i][0] = dp[i - 1][0]\)
• \(dp[i][1] = dp[i - 1][1] + (dp[i - 1][0])\)

If \(s_i\) = ?,

• \(dp[i][0] = dp[i - 1][0] + (dp[i - 1][1])\)
• \(dp[i][1] = dp[i - 1][1] + (dp[i - 1][0])\)

Note that the final answer is \(dp[n][0] + dp[n][1] - 2\).

And the matrices will be:

\(A_0 = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}, A_1 = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}, A_? = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}\)

Thus, we reduced the size of the matrix from \(3\times 3\) to \(2\times 2\).