Gọi $f[i][j]$ là số lượng xâu thoã mãn có độ dài là $i$ và có kí tự cuối cùng là $j$ (tức là kí tự thứ $i$ của xâu có độ dài $i$ là $j$). ta biết trước được là:

• $f[1][0]=1.$
• $f[1][1]=1.$
• $f[1][2]=1.$

Khi đặt một kí tự $0$ hoặc $2$ vào vị trí cuối cùng là $i$ thì sẽ có $f[i-1][0]+f[i-1][1]+f[i-1][2]$ xâu.

Khi đặt một kí tự $1$ vào vị trí cuối cùng là $i$ thì sẽ có $f[i-1][0]+f[i-1][2]$ xâu.

Kết quả sẽ là $f[n][0]+f[n][1]+f[n][2]$.