Introduction

In this blog post, we will explore how to solve the LeetCode problem "198" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. Example 1: Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4. Example 2: Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12. Constraints: 1 <= nums.length <= 100 0 <= nums[i] <= 400

Explanation

Here's a breakdown of the solution and the Python code:

• High-Level Approach:

  • Dynamic Programming: Use dynamic programming to build up the solution incrementally.
  • Optimal Substructure: The maximum amount you can rob up to house i is either the maximum you could rob up to house i-1 (not robbing house i) or the maximum you could rob up to house i-2 plus the amount in house i (robbing house i).
  • Overlapping Subproblems: The same subproblems are solved multiple times, so memoization (storing previously calculated results) is employed.

• Complexity:

  • Runtime Complexity: O(n)
  • Storage Complexity: O(n) - can be optimized to O(1)

Code

    def rob(nums):
    """
    Calculates the maximum amount of money you can rob without robbing adjacent houses.

    Args:
        nums: A list of integers representing the amount of money in each house.

    Returns:
        The maximum amount of money you can rob.
    """
    n = len(nums)

    if n == 0:
        return 0
    if n == 1:
        return nums[0]

    # dp[i] stores the maximum amount that can be robbed up to house i
    dp = [0] * n

    # Base cases
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    # Iterate through the houses, building up the solution
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[n - 1]