[DP - 1D, Medium] House Robber

https://leetcode.com/problems/house-robber/?envType=study-plan-v2&envId=leetcode-75

중복이다. 다른 시리즈에서 풀었다.
https://velog.io/@potato_song/DP-Medium-House-Robber

요약

• 초기화:
  • dp[0] = nums[0]: 첫번째 집 터는 경우
  • dp[1] = Math.max(nums[0], nums[1]): 둘 중 더 큰 집을 터는 경우
• 터는 선택지, 안 터는 선택지 중 max를 전개해나간다.
  • dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
  • 인접한 집은 못터니까.

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n <= 1) return nums[0];

        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i=2; i<n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[n - 1];
    }
}