Return the maximum amount of money you can rob tonight without alerting police (cannot rob adjacent houses).

Example 1:

• Input: nums = [1,2,3,1]
• Output: 4

Constraints:

• 1 <= nums.length <= 100

rob[i] = max(rob[i-1], rob[i-2] + nums[i]).

1D Dynamic Programming (Skip Adjacent)

graph TD
    Problem["Problem of Size N"] --> Sub["Break into Subproblems DP[i]"]
    Sub --> Base["Base Cases: DP[0], DP[1]"]
    Base --> Trans["State Transition: DP[i] = f(DP[i-1], DP[i-2], ...)"]
    Trans --> Table["Fill DP Table / Variables"]
    Table --> Result["Return DP[N]"]

function rob(nums) {
  let rob1 = 0, rob2 = 0;
  for (const n of nums) {
    let temp = Math.max(n + rob1, rob2);
    rob1 = rob2;
    rob2 = temp;
  }
  return rob2;
}

• Time Complexity: O(n)
• Space Complexity: O(1)
• Explanation: Two variable DP.

function rob(nums) {
  let rob1 = 0, rob2 = 0;
  for (const n of nums) {
    let temp = Math.max(n + rob1, rob2);
    rob1 = rob2;
    rob2 = temp;
  }
  return rob2;
}

• Time Complexity: O(n)
• Space Complexity: O(1)
• Explanation: Constant space DP.

1. Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
2. Iterate & Evaluate: Process the input according to the boundary conditions.
3. Update & Return: Compute the optimal answer and return early or at termination.

Maintain two pointers rob1 and rob2 representing max loot skipping current vs taking current.

1. Track max profit up to house i-1 and house i-2.

👉 Solve this problem interactively in the DSA Lab