左から値を1つずつ確定させていくことを考えます。 i−1i-1i−1 番目まで確定し、次に iii 番目の値を決める時、既に確定している数列としてあり得るものは 3i−13^{i-1}3i−1 通りあるのでこれを全部持つことは出来ませんが、 iii 番目にどの値を置けるかの判定に必要なのは直前の M−1M-1M−1 個の値の情報だけなので、以下のようなdpが出来ます。 dp[i][j]=dp[i][j] = dp[i][j]= iii 番目まで確定し、直前の M−1M-1M−1 個の数列が jjj であるような数列のうち今のところ条件を満たしているものの個数 計算量は O(N3M)O(N3^M)O(N3M) です。