injoon2018   2년 전

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

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

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

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

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

원리가 궁금합니다

djm03178   2년 전

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

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

injoon2018   2년 전

아 감사합니다 

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

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