Pythonでの動的プログラミングの問題1
8688 ワード
金鉱問題
質問する
手記コード
コード#コード#
# 테스트 케이스(Test Case) 입력
for tc in range(int(input())):
n, m = map(int, input().split()) # 3*4 행렬
array = list(map(int, input().split())) #1 3 3 2 2 1 4 1 0 6 4 7
# 3*4 행렬 만들기
dp = []
index = 0
for i in range(n):
dp.append(array[index:index + m])
index += m
print("dp : ", dp)
# 다이나믹 프로그래밍 진행
for j in range(1, m):
for i in range(n):
# 왼쪽 위에서 오는 경우
if i == 0:
left_up = 0
else:
left_up = dp[i - 1][j - 1]
print("left_up : ",left_up)
# 왼쪽 아래에서 오는 경우
if i == n - 1:
left_down = 0
else:
left_down = dp[i + 1][j - 1]
print("left_down : ", left_down)
# 왼쪽에서 오는 경우
left = dp[i][j - 1]
dp[i][j] = dp[i][j] + max(left_up, left_down, left)
print("left : ", left)
print("new_dp : ", dp)
result = 0
for i in range(n):
result = max(result, dp[i][m - 1])
print("answer : ", result)
答え
ソース
就職のためのコードテストwith Python(羅東彬著)
Reference
この問題について(Pythonでの動的プログラミングの問題1), 我々は、より多くの情報をここで見つけました https://velog.io/@9566/다이나믹-프로그래밍-문제1-in-pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol