Imagine you’re a professional thief, planning to rob houses along a street. Each house is filled with a certain amount of cash, but there’s a catch - the houses have interconnected security systems. If two adjacent houses are broken into on the same night, the alarm will go off. Given an array of non-negative integers representing the cash in each house, your task is to calculate the maximum amount of money you can steal in one night without setting off the alarms.

Let’s say the amount of money in each house is represented by the elements in an array nums. If you choose to rob the first house (num[0]), your next options are the third or fourth house (num[2] or num[3]). If you choose the second house (num[1]), your next options are the fourth or fifth house (num[3] or num[4]).

If we use recursion to solve this problem, num[3] will be calculated multiple times, which is inefficient. This leads us to consider using dynamic programming to solve this problem.

In other words, for each house, we calculate the maximum profit if we choose to rob that house. Let’s start from the house with the highest number:

Remaining Maximum House Number Maximum Profit Denoted as
0 num[0] dp[0]
1 max(num[0],num[1]) dp[1]
2 max(num[2]+dp[0],dp[1]) dp[2]
3 max(num[3]+dp[1],dp[2]) dp[3]
4 max(num[4]+dp[2],dp[3]) dp[4]
… … …
n max(num[n]+dp[n-2],dp[n-1]) dp[n]

Here’s how we can implement this in JavaScript:

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

This algorithm ensures that we’re always choosing the option that gives us the maximum profit, while avoiding the risk of setting off the alarms. It’s a perfect example of how dynamic programming can help us solve complex problems in an efficient way.