概要
競プロ典型90問の解説記事です。
解説の画像を見ても分からない（理解力が足りない）ことが多々あったので、後で解き直した際に確認できるようまとめました。
※順次、全ての問題の解説記事を挙げていく予定です。
※★５以上の問題は難易度的に後回しにしているため、投稿時期が遅くなる可能性があります。（代わりに丁寧に解説してくれる方いたらぜひお願いします）
問題008-AtCounter
問題概要
文字列Sから任意の文字を順番を変えずに取り出したときに、"atcoder"(以下、文字列Tとします。)となる個数を求める。
解き方
まず初めに、単純にSから"atcoder"の文字をそれぞれ検索する方法が考えられますが、
この考えでは、文字列の長さNの検索を7回（Tの長さ分）行うため、$N^7$となりTLEになってしまいます。
そこで今回は、DP（動的計画法）を用います。
dp[i][j]を、Sのi文字目までを用いた時、Tのj文字目までを作る通りの数と定義します。
そうすると、
１. $S[i] = T[j]$の時（Sのi文字目とTのj文字目が等しい時）
$dp[i][j] = dp[i-1][j-1] + dp[i-1][j]$
※Sのi文字目を使ってTのj文字にする時と、Sのi文字を使わずにj文字目まで作った時の和です。
２. $S[i] ≠ T[j]$の時（Sのi文字目とTのj文字目が等しくない時）
$dp[i][j] = dp[i-1][j]$
※Sのi-1文字目までを使ってTのj文字を作る通り数と同じです。
の２つの漸化式が求められます。
また、j=0の時は、文字を取り出さない方法、すなわち１通りとできるので、
$dp[i][0] = 1$
i=0の時（かつj≠0）の時は、Sを１文字も使わず、Tのj文字まで作ることは出来ないため、
$dp[0][j] = 0$
と考えられます。ここまで求められると、i, jを小さい順から計算することで、
全てのi, jに対してdpを求めることができ、dp[N][7]が答えとなります。
引用元：競プロ典型90問 Github
実装
# 入力の受け取り
N = int(input())
S = input()
# 今回はatcoderをTとする
T = "atcoder"
# 余りのための変数
mod = 10**9+7
#0文字からN文字まで考えるので、"+1個"配列を定義
dp = [[0]*(len(T)+1) for _ in range(N+1)]
# j=0の時、全て1を代入
for i in range(N+1):
dp[i][0] = 1
# S[i]がT[j]に等しいかで場合分け
# dpのiとS[i]で示すiが1ズレている点に注意（jも同様）
# 答えをmodで割った余りを格納
for i in range(N):
for j in range(len(T)):
if S[i] == T[j]:
dp[i+1][j+1] = dp[i][j] + dp[i][j+1]
dp[i+1][j+1] %= mod
else:
dp[i+1][j+1] = dp[i][j+1]
dp[i+1][j+1] %= mod
# N文字まで使って、Tになる時の通り数を出力
print(dp[N][len(T)])
最後に
問題の解説を読んでも他の人のコードを見てもさっぱり分からないという方の
力に少しでもなれれば幸いです。
コードの改善点やその他、ご意見などあれば、気軽にコメントください。
また、この記事を読んで理解できた方はぜひLGTMを押していただけると嬉しいです。
（記事投稿のモチベになります。）
ここまでお読みいただきありがとうございました。