이동식 저장소

1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다. www.acmicpc.net 게임판을 탐색하는 전형적인 동적 계획법 문제이다. 어떤 칸에서 시작하여 게임을 진행할 수 있는 최대 횟수는 정해져 있으며, 그러한 횟수가 변하지 않기 때문에 한번 계산한 결과를 계속해서 써먹을 수 있고, 그래야만 한다. 메모이제이션 없는 완전 탐색의 시간복잡도는 $O(4^{nm})$이다. 실제로는 구멍에 빠지는 등의 종료로 인해 더 작겠지만 전체적으로 보면 지수 꼴의 시간 복잡도를 갖는다. 단 여기서 사이..