この問題は、動的計画法(DP)によって解くことができます。この解説では \(2\) 種類の方針を説明します。

以下の解説では、各桁が \(1\) 以上 \(9\) 以下の整数であって、隣合う桁の差が \(1\) 以下であるようなものを「平坦数」と呼びます。

方針1: 漸化式を立ててDPを設計する

例として、最初のサンプルで考えてみましょう。
\(4\) 桁の平坦数は何個あるでしょうか？

そのようなものの個数を、場合分けによって数えてみましょう。
いろいろな場合分けの方法がありますが、例えば先頭の桁が何であるかによって場合分けするというのが自然な方法の一つです。
例えば、最初の桁を \(7\) とするとどうなるでしょうか？

\(7???\)

この場合、後ろの \(3\) つの \(?\) を埋めて平坦数にする方法が何通りかを求めたいです。 この答えを、 \(f(7???)\) と書くことにしましょう。

これも簡単には求まらないので、さらに場合分けを進めてみます。
次は二番目の桁で場合分けをしてみるのが自然な発想です。 条件より、二番目の桁は \(6, 7, 8\) のいずれかでなければなりません。

\(76??\)
\(77??\)
\(78??\)

つまり、 \(f(7???) = f(76??) + f(77??) + f(78??)\) となります。

ここで、 \(76??\) の \(?\) を平坦数になるように埋める方法の個数は、 \(6??\) の \(?\) を平坦数になるように埋める方法の個数と等しいです。( \(76??\) の先頭の \(7\) は、これ以降の \(?\) を埋める際に影響を及ぼしません。)

\(f(76??) = f(6??)\)

ということになります。これと上の考察とを合わると、

\(f(7???) = f(6??) + f(7??) + f(8??)\)

という\(f\) に関する簡単な漸化式が得られました。

ここからは、この漸化式を繰り返し適用します。 たとえば、上の式の右辺を求めるために \(f(6??)\) を知りたい場合は、ここまでと同様な考えで得られる

\(f(6??) = f(5?) + f(6?) + f(7?)\)

という式を用います。 このように繰り返していく時、 \(f\) の中に入るものは、常に先頭だけが数字で残りが \(?\) であるものに出来ることに注目してください。
そこで、そのような形で書けるものに対する \(f\) の値を全て順番に求めていくことにします。

二次元配列 \(dp[][]\) を作り、 \(dp[n][k]\) には \(f(k??? \dots???)\) (括弧の中身は、先頭が \(k\) で、その後ろに \(?\) が \(n-1\) 個並ぶ文字列) の値を入れます。 たとえば、 \(dp[4][7] = f(7???)\) です。 先程求めた漸化式を用いると、 \(dp[4][7] = dp[3][6] + dp[3][7] + dp[3][8]\) となります。

この配列を正しい値で埋めるためには、どのようにすればよいでしょうか？
例えば、 \(dp[4][7]\) を正しく求めるためには、 \(dp[3][6], dp[3][7], dp[3][8]\) の値が既に正しく求まっている必要があります。
今回の場合は、n の小さい順に埋めていけばよいです。(一般に、DPを設計する際は配列の埋める順番や埋め方に注意してください。)

具体的な実装は以下のようになります。

• \(n = 1, 1 \le k \le 9\) に対して、 \(dp[n][k] = 1\) とする
• 次に \(2\) 以上の \(n\) に対して、 \(n\) の小さい順にループを回し、 \(dp[n][k]\) の値を埋めていく
  • 例えば、 \(dp[4][7] = dp[3][6] + dp[3][7] + dp[3][8]\) とする。

ただし、 \(k = 1\) または \(k = 9\) のときは実装上注意が必要です。 詳しくは、解説ページ最下部の実装例を参考にしてください。

方針2: 平坦数の全列挙から解法を導く

まず、 \(N\) 桁の平坦数をうまく全列挙する方法を考えてみましょう。
\(list[D][r]=\) (末尾が \(r\) である \(D\) 桁の平坦数の集合) とし、これを \(D\) の小さい方から順に求めていきます。

明らかに、 \(list[1][i]=\{i\}\) なのでここから始めます。
\(list[D]\) の各要素の末尾に桁をひとつ付け加えることにより、 \(list[D+1]\) を作成することを考えましょう。
明らかに、「 \(X\) が \(D+1\) 桁の平坦数である」ならば「 \(X\) の上から \(D\) 桁のみに着目してもその数は平坦数」です。なので、 \(list[D+1]\) に含まれるべき要素は \(list[D]\) に含まれる要素の末尾にひとつ桁を追加することで作ることができ、さらに、 \(D\) 桁の平坦数の末尾に桁を追加した際に \(D+1\) 桁の平坦数となる必要十分条件は、 \(D\) 桁の平坦数の末尾と追加する桁との差が高々 \(1\) であるということが分かります。
よって、この時行うべきことは以下です。

• 整数 \(1 \le i \le 9\) について、以下を行う。
  • 整数 \(\max(1,i-1) \le j \le \min(9,i+1)\) について、以下を行う。
    • \(list[D][i]\) の全ての要素 \(E\) について、 \(E\) の末尾に \(j\) を付けたものを \(list[D+1][j]\) に加える。

例えば、 \(list[2][9]=\{89,99\}\) であり、 \(list[3][8]\) に \(list[2][9]\) の全要素の末尾に \(8\) を追加したものである \(\{898,998\}\) を追加するといったことを \(D\) の小さい方から順次行っていきます。
最終的な \(N\) 桁の平坦数の集合は \(list[N]\) 全体です。
ここで、当たり前ですが重要な事実として、 \(list[D]\) 全体の要素が全て相異なる時 \(list[D+1]\) 全体の要素も全て相異なります。
よって、漏れなくダブりなく平坦数を列挙することができることが分かりました。

ですが、もちろん空間計算量的にも時間計算量的にも集合を管理するわけにはいかないので、条件を満たす整数の個数だけを求めます。

\(dp[D][r]=\) (末尾が \(r\) である \(D\) 桁の平坦数の 個数 ) を順次計算していくことを考えます。
これは、先程 \(list\) を作成した時の集合の要素数だけを計算していくことで求められます。本質的には \(list\) の作成と同じなのでこれ以上の詳細は省略します(実装例を参照してください)。

注意事項として、 \(998244353\) で割った余りをとる必要があることに注意してください。これは、 \(dp\) を常に \(998244353\) で割った余りとして求めていくことで実現可能です。

実装例(C++):

#include<bits/stdc++.h>
#define mod 998244353

using namespace std;

int dp[1048576][10]={0};

int main(){
  int n;
  cin >> n;
  for(int i=1;i<=9;i++){dp[1][i]=1;}
  for(int d=2;d<=n;d++){
    for(int i=1;i<=9;i++){
      for(int j=max(1,i-1);j<=min(9,i+1);j++){
        dp[d][j]+=dp[d-1][i];
        dp[d][j]%=mod;
      }
    }
  }
  int res=0;
  for(int i=1;i<=9;i++){
    res+=dp[n][i];
    res%=mod;
  }
  cout << res << '\n';
  return 0;
}