[アルゴリズム]

840 ワード

アルゴリズムの問題を解くテキストリンク

これがエンコードテスト#32です

前回解いた#31と似ているので、似たような問題が解けました.

アルゴリズム#アルゴリズム#

ダイナミックプログラミングデータム
(x,y)の値に(x-1,y)または(x-1,y-1)が加算される場合があります.
そこでdp[i-1][j],dp[i-1][j-1]では,dp[i]dp[j]に最値を加算するように解く.

(例外1)の最後の列の場合、dp[i-1][j]値は存在しません.

(例外2)の第1列の場合、dp[i-1][j-1]の値は存在しません.

n= int(input())
dp=[]
for _ in range(n):
    dp.append(list(map(int,input().split())))
for i in range(1,n):
    temt=0
    for j in range(len(dp[i])):
        if j==len(dp[i])-1:
            temt=dp[i-1][j-1]
        elif j==0:
            temt=dp[i-1][j]
        else:
            temt=max(dp[i-1][j],dp[i-1][j-1])
        dp[i][j]+=temt
print(max(dp[n-1]))

時間の複雑さ

O(n x n)->500 x 500->250000
タイムアウト2秒
毎秒1億回、処理できます!

Reference

この問題について([アルゴリズム]), 我々は、より多くの情報をここで見つけました https://velog.io/@pinoa1228/알고리즘

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

!unzip-q-o zipファイルを開く

export default ってなに？