[BOJ 11048]モバイル(Python)

質問する

移動

問題の説明

これは二次元DPを用いて解決される典型的な問題である.法規は右側、下側、対角線に移動できますが、対角線を移動する必要はありません.
問題は一番多く食べられるキャンディの数だからです.だからDPを計算するときは左上だけ見て
だから2次元DPを作って、席に着いたら、一番食べられるキャンディの数を更新すればいいのです.点火式は以下の通りです.
dp[i][j]=max(dp[i-1][j]+dp[i][j-1])+(i,j)糖水
また、ex)i-1の範囲のハンドルが必要であれば、DPの大きさを+1に設定することができる.

プールコード

n, m = map(int, input().split())
dp = [[0] * (m + 1) for _ in range(n + 1)]
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

# dp 채우기
for i in range(1, n + 1):
    for j in range(1, m + 1):
        # 위, 왼쪽 중 큰값
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + graph[i - 1][j - 1]

print(dp[n][m])