公式解説と同様の方針で、辞書を使わず DP の状態を持つ方法を示します。

「最後に見た \( W\) 個のマスの数字の書き方」を整数にエンコードするとき（エンコードされた値を「状態番号」と呼ぶことにします）、直前に見たマス \((i,j-1)\) が先頭桁に、古いマス \((i-1,j)\) が 1 の位にくるようにします。

するとDP テーブルの状態番号がソートされているとき、DP の遷移を「 1 を置く」「 2 を置く」「 3 を置く」の順に行えば、DP の遷移先の新しい状態番号は広義単調増加になります。よって DP テーブルを (状態番号, 場合の数) のペアを要素に持つ動的配列で持てば、遷移は「DPテーブルの末尾の場合の数に加算する」or「DPテーブルの末尾に新しい(状態番号, 場合の数)を追加する」で行え、その結果新しい DP テーブルの状態番号もソートされた状態になります。

実装例（Pypy3）

https://atcoder.jp/contests/abc379/submissions/59634379