質問する

白駿1932号整数三角形

に答える

ソリューション

特定の位置に到達するには、「左上」または「真上」の2つの位置からしか降りられません.
したがって、最大の最適と(すべての場所から前の2つの場所まで)がある場合は、
dp[i][j]=array[i][j]+max(dp[i−1][j−1],dp[i−1][j])dp[i][j]=array[i][j]+max(dp[i-1][j-1], dp[i-1][j])dp[i][j]=array[i][j]+max(dp[i−1][j−1],dp[i−1][j])

注意事項

にアクセスするたびに、

がリストの範囲を超えているかどうかを確認します.

は、配列を単独で使用することなく、DPテーブルに初期データを入れる、DPテーブル

を点火式に更新するための便利な実施である.

に感銘を与える

dynamicとgreedyはどんな違いがあって、解釈ははっきりしません

このラベルを読み、再理解します。

低点火方式をどのように確保するかを直感的に理解していない.

すべての状況を探索し、オーバーラップの代わりに理解する(劉南生…?フィボナッチと考えてください)

に答える

n = int(input())
dp = [] #다이나믹 프로그래밍을 위한 DP 테이블 초기화

for _ in range(n):
	dp.append(list(map(int, input().split())))

# 다이나믹 프로그래밍으로 두 번째 줄 부터 내려가면서 확인
for i in range(1, n) :
	for j in range(i+1):
		# 왼쪽 위에서 내려오는 경우
		if j == 0 :
			up_left = 0 # 범위에서 벗어남
		else :
			up_left = dp[i-1][j-1]  # 값 저장
		# 바로 위에서 내려오는 경우
		if j == i :
			up = 0 # 범위에서 벗어남
		else :
			up = dp[i-1][j] # 값 저장
		# 최대 합으로 저장
		dp[i][j] = dp[i][j] + max(up_left, up)

print(max(dp[n-1]))

出力コードの理解