198. House Robber

198. House Robber

https://leetcode.com/problems/house-robber/

문제

풀이(Recursion)

일반적인 탑다운 방식으로 푸는 방법으로 Take, Non Take일 때를 나누어서 생각한다. 만약 Take하면 다음에는 무조건 건너 뛰어야 하고 NonTake 뒤에는 마찬가지로 Take, Non Take일 떄를 생각하면 된다.

Take 여부는 isRob이고 Rob가 True이면 건너 뛰어야 하고 그렇지 않으면 Take, Non Take를 탐색하여야 한다.

풀이(DP)

Take, Non Take 경우를 생각해야 한다. Non Take되었을 때에는 dp[i-2] + num[i]일 것이고 Take일 때에는 dp[i-1]일 것이다. 이 두개 중 최대값을 저장하면 된다.