耳dpについて
- みんなのプロコン2019「Ears」で出題されたdpだから耳dp
lcsに近い概念だけど、lcsでは表現できない対象となる文字列に特定の文字を構成できる組み合わせが何通りあるか、など、通り数を数えることができる- いざ使おうとすると、なかなか出てこない
概要図
例; 競プロ典型90問からの引用
問題
解答
import collections
N=int(input())
S= input()
MOD = 1000000007
def mimi_dp(s1, s2):
'''
references:
- https://github.com/E869120/kyopro_educational_90/blob/main/editorial/008.jpg
'''
n1, n2 = len(s1), len(s2)
dp = [[0]*(n2+1) for _ in range(n1+1)]
dp[0][0] = 1
for i in range(n1):
for j in range(n2+1):
dp[i+1][j] += dp[i][j] # 下に流す
for j in range(n2):
if s1[i] == s2[j]: # 同じならば
dp[i+1][j+1] += dp[i][j] # 加えていく
for j in range(n2+1): # 横をMOD
dp[i+1][j] %= MOD
print(dp[n1][n2])
mimi_dp(s1=S, s2="atcoder")
例; ほとんど同じ問題
問題
解説
- dpっぽさがあるが耳dpであることにたどり着けなかった
- 文字の表現の個数なので耳dpが解の候補になる
解答
S= input()
MOD = 1000000007
def mimi_dp(s1, s2):
n1, n2 = len(s1), len(s2)
dp = [[0]*(n2+1) for _ in range(n1+1)]
dp[0][0] = 1
for i in range(n1):
for j in range(n2+1):
dp[i+1][j] += dp[i][j] # 下に流す
for j in range(n2):
if s1[i] == s2[j]: # 同じならば
dp[i+1][j+1] += dp[i][j] # 加えていく
for j in range(n2+1): # 横をMOD
dp[i+1][j] %= MOD
print(dp[n1][n2])
mimi_dp(s1=S, s2="chokudai")