해당 포스팅은 릿코드의 198. House Robber 문제 풀이 다룬다. 문제 링크
코드는 javascript로 작성하였으며 dp로 풀이하였다.

문제

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

강도가 집들을 털려고 한다.
인접한 집들의 경우 하나만 털 수 있다.
강도가 털 수 있는 최대 돈은?

풀이

예제 1에서 각 집들이 가진 돈이 [1,2,3,1]로 주어진다.
인접한 집은 털 수 없으므로 한칸 건너서 털 수 있다.
각 dp[n]이 최대가 되기 위해서는 아래의 공식을 따른다.

DP 공식

전체 코드

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const dp = [...Array(nums.length)].fill(0);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    
    for (let i=2; i<nums.length; i++) {
        dp[i] = Math.max((dp[i-2] + nums[i]), dp[i-1]);
    }
    return dp[nums.length-1];
};