글 읽기 - 접근 방법 질문요

이게 어떻게 다이나믹 프로그래밍으로 풀 수 있는지 원리가 궁금합니다

n번째 줄까지 최대의 합을 구하는 방법이 'A'라하더라도

n+1번째 줄까지의 최대의 합을 구하는 방법은 'A'에서 좌우로 뻗어있는 두개의 선택지가 아닌

전혀다른 B의 길로 가서 답이 나올 수도 있지않나요?

만약 그렇게된다면 메모이제이션이 쓸모가 없지않나요??

원리가 궁금합니다

'몇 번째 줄'까지의 최적의 답을 구하는 것이 아니라, 'A라는 칸'까지의 최적의 답을 구하는 것입니다. 즉, 모든 칸에 대해 개별적인 메모이제이션을 해야 됩니다.

이렇게 메모이제이션을 하면, 맨 아랫줄에 저장된 값들 중 최댓값이 정답이 되겠죠?

아 감사합니다

왠지 아무리 생각해도 어떻게 메모이제이션을 써야할지 안떠올르더라구요

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge