ABC232(M-SOLUTIONS) D - Weak Takahashi

atcoder.jp

大事故でした。。。
貰うDPと配るDP、久々に書いたので、両方混ざって、間に合わないという大失態。

今だとアルゴ式（貰う DP と配る DP | アルゴ式）を参照した方がいい気もするが、
新鮮なうちに両方のPython解を書いて載せておきます。

※問題そのものの考察については、いろんな解説が充実しているので、省略で！

配るDP

def resolve():
    H,W=map(int,input().split())
    C=[]
    for i in range(H):
        C.append(input())

    dp=[[-1000000]*(W) for i in range((H))]
    
    if C[0][0]==".":    
        dp[0][0]=1
    for h in range(0,H):
        for w in range(0,W):
            if h<H-1:
                if C[h+1][w]==".":
                    dp[h+1][w]=max(dp[h][w]+1,dp[h+1][w])
            if w<W-1:
                if C[h][w+1]==".":
                    dp[h][w+1]=max(dp[h][w]+1,dp[h][w+1])
 
    Max=0
    for h in range(H):
        for w in range(W):
            Max=max(Max,dp[h][w])

    print(max(0,Max))

resolve()

貰うDP

def resolve():
    H,W=map(int,input().split())
    C=[]
    for i in range(H):
        C.append(input())
 
    dp=[[-1000000]*(W) for i in range((H))]
    
    if C[0][0]==".":    
        dp[0][0]=1
    for h in range(0,H):
        for w in range(0,W):
            if C[h][w]==".":
                if h>=1:
                    dp[h][w]=max(dp[h-1][w]+1,dp[h][w])
                if w>=1:
                    dp[h][w]=max(dp[h][w-1]+1,dp[h][w])
 
    Max=0 
    for h in range(H):
        for w in range(W):
            Max=max(Max,dp[h][w])

    print(max(0,Max))

resolve()