Teaching Kids Programming – Dynamic Programming Algorithms to Obtain Max Non-Neighbour Values

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine 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:
0 <= nums.length <= 100
0 <= nums[i] <= 400

Basically, we are to pick the numbers from the array, but any two neigbour/consecutive numbers cannot be picked. We can bruteforce with Depth First Search or Breadth First Search, but the time complexity is not optimal and as we may search non-optimal branch – e.g. skipping any consecutive numbers.

Note: picking the largest won’t work for example, given [7, 9, 8], the optimial solution would be to pick 7 and 8 instead of picking the largest 9.

Top Down Dynamic Programming Algorithm to Compute the House Robber Problem

Given F(n) denote the max numbers we can get up to n-th house, we know if we pick current n-th value, the total value will be and if we don’t pick n-th value, we have . Thus picking the max of two gives the value of F[n].

And and

Given we have the Dynamic Programming Algorithm, we can implement it using Recursion with Memoization – which is Top Down. Remember we have to use @cache or @lru_cache(None) to avoid re-calculating the intermediate values.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def rob(self, nums: List[int]) -> int:
        @cache
        def f(n):
            if n == 0:
                return nums[0]
            if n == 1:
                return max(nums[0], nums[1])
            return max(f(n - 1), f(n - 2) + nums[n])
        if len(nums) == 0:
            return 0
        return f(len(nums) - 1)

class Solution:
    def rob(self, nums: List[int]) -> int:
        @cache
        def f(n):
            if n == 0:
                return nums[0]
            if n == 1:
                return max(nums[0], nums[1])
            return max(f(n - 1), f(n - 2) + nums[n])
        if len(nums) == 0:
            return 0
        return f(len(nums) - 1)

Bottom-up Dynamic Programming Algorithm to Compute the House Robber Problem

Given the Dynamic Programming Equation, we can compute it in bottom-up manner using Iteration:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        if n == 2:
            return max(nums[0], nums[1])
        f = [0] * n
        f[0] = nums[0]
        f[1] = max(nums[0], nums[1])
        for i in range(2, n):
            f[i] = max(f[i - 1], f[i - 2] + nums[i])
        return f[-1]

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        if n == 2:
            return max(nums[0], nums[1])
        f = [0] * n
        f[0] = nums[0]
        f[1] = max(nums[0], nums[1])
        for i in range(2, n):
            f[i] = max(f[i - 1], f[i - 2] + nums[i])
        return f[-1]

Both Dynamic Programming Algorithms are in O(N) time and O(N) space. As for each F[i] for i between (0, n), we only calculate once (and re-use it later with Memoziation or the array).

Largest Sum of Non-Adjacent Numbers (House Robber or Disappearing Coins): Dynamic Programming Algorithms

• Teaching Kids Programming – Dynamic Programming Algorithms to Compute the Maximum Non-Adjacent Tree Sum
• C++ Dynamic Programming Algorithm to Compute the Largest Sum of Non-Adjacent Numbers in a Circular Array
• How to Maxmize Profits to Robbering in a Binary Tree using Dynamic Programming Algorithm?
• Using the Dynamic Programming Algorithm, the Depth First Search or Breadth First Search to Solve House Robber Problem
• Teaching Kids Programming – Largest Sum of Non-Adjacent Numbers (2D Version – Disappearing Coins in a Matrix)

–EOF (The Ultimate Computing & Technology Blog) —