TIL 0814:: boj 11048

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
arr = [[0]*(m+1)] + [[0]+list(map(int,input().split())) for i in range(n)]
dp = [[0]*(m+1) for i in range(n+1)]
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])+arr[i][j]
print(dp[n][m])

 

 

 

 

당연히 bfs/dfs 중 하나라고 생각했는데…. 찾아보니 dp라는 것을 활용하는 문제였다

https://velog.io/@khjcode/알고리즘-DP-문제-풀기-파이썬#dp-란-무엇인가

알고리즘 DP 문제 풀기 ( 파이썬 )

 

정해진 규칙에 따라 이동할 때, 가져올 수 있는 사탕의 최댓값을 출력하는 문제이다.

 

 

 

점화식:

 

dp[i][j] = max(dp[i-1][j], dp[i][j-1])+arr[i][j]

 

인덱스를 맞춰주기 위해 0으로 이루어진 패딩 배열을 덧붙인 것. 처음에 이해하지 못했음