AtCoder Beginner Contest 211 C - chokudai【Python】
https://atcoder.jp/contests/abc211/tasks/abc211_c
AtCoder ProblemsのRecommendationで Difficulty: 559、Solve Probability:40%でした。
全くわからず、解説で動的計画法を用いるという情報を見た上でも解けませんでした。
公式の解説動画
https://www.youtube.com/watch?v=Zu9S_kJ-7tk
を何度も見返してやっとある程度理解できたというレベルの問題でした。
MOD=10**9+7 S = input() t = "chokudai" DP = [[0] * (len(S)+1) for _ in range(len(t)+1)] DP[0] = [1] * (len(S)+1) for i in range(1, len(t)+1): for j in range(1, len(S)+1): if S[j-1] != t[i-1]: DP[i][j] = DP[i][j-1] else: DP[i][j] = (DP[i][j-1] + DP[i-1][j-1]) % MOD print(DP[-1][-1])