[Leetcode][576] Out of Boundary Paths

문제 : https://leetcode.com/problems/out-of-boundary-paths/

---

DP. 메모이제이션이 필요하다.

남은 maxCount 횟수, 현재 좌표가 같다면 정답 횟수는 같아진다. 

즉, dp[maxCount][row][column] = 경계를 벗어나는 경로 횟수 를 저장한다.

 

dp[maxCount][row][column] = dp[maxCount-1][row][column+1] 
               + dp[maxCount-1][row][column-1]
               + dp[maxCount-1][row+1][column]
               + dp[maxCount-1][row-1][column]

이동은 상하좌우로 할 수 있기 때문에 점화식은 다음과 같다.

더한 값에 1000000007을 나눈 나머지값을 저장해줘야한다.

 

만일 row, column이 경계를 벗어난 값이면 dp 값은 1이된다.

maxCount가 0가 되었는데도 경계를 벗어나지 못했다면 0이 된다.

 

시간복잡도는 메모이제이션으로 동일한 배열값을 탐색하지 못하게 막았기 때문에 배열 크기만큼 걸린다.

즉, O(maxCount * row * column).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/576.%20Out%20of%20Boundary%20Paths.cpp