[DP] House Robber

단순한 DP문제라서 설명없이 바로 풀어본다

 

이때 dp[ i ]는 length가 i일때 최대값이라는 것에 주의하자.

경험상 dp는 내가 만드는 index 배열의 의미를 유념하는 것이 중요한 것 같다.

length가 i일때 최댓값은

dp[i-1]와 dp[i-2]+i값 중 더 큰 값이다.

이게 사실 dp의 핵심인데

이미 dp[i-1]과 dp[i-2]는 완벽하게 계산된 값이라는 전제하에,

dp[i-1]은 nums[i]을 더하지 못하지만 dp[i-2]는 더할 수 있으므로, 그 둘 중 더 큰 값이 무엇인지 생각해내는 것이다.