zjvlzld   4년 전

dp초기화를 -1로 하면 잘 돌아가는데 0으로 하면 안돌아가게 되네요... 이유가 뭘까요??

aung   4년 전

저도 방금알았는데요,

dp배열 값을 -1로 초기화 시켜놓고 값을 구했을 때 아에 목적지에 도달 불가능한 경우가 생깁니다. 그걸 dp[r][c] = 0 이라고 계산해놓는다면

다음번에 같은 위치에 재귀가 들어갔을 때, 0을 반환하게 되겠죠

그러나 dp배열 값을 0으로 초기화 시켜놓고 값을 구하면, 현재 위치에서 목적지까지의 경로가 없을 경우 또한 dp[r][c] = 0이므로 반복적으로 재귀를 호출하는 경우로 인해

시간초과가 난다는 것을 알게 되었습니다.

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