Home
Using the Dynamic Programming Algorithm, the Depth First Search or Breadth First Search to Solve House Robber Problem (Largest Sum of Non-Adjacent Numbers)
Tags:, , , , , , , , , , ,

Using the Dynamic Programming Algorithm, the Depth First Search or Breadth First Search to Solve House Robber Problem (Largest Sum of Non-Adjacent Numbers)

April 15, 2015 3 Comments algorithms, BFS, Breadth First Search, c / c++, Depth First Search, DFS, dynamic programming, Dynamic Programming, Memoization, python, Recursion

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.

This is a typical puzzle that can be solved using Dynamic Programming.

The restriction is that you can’t use two consecutive numbers (in an array) in a row. You can jump like this, 1, 3, 5, 7 or 2, 4, 6, 8. And you could also skip more than 1 number. We can do a one-pass scan from left to right, and compute the maximum values to that position.

So, the formula (Dynamic Programming) is:

1
2
3

f(x) = max(f(x - 1), f(x - 2) + num(x)) 
f(0) = num(0)
f(1) = max(num(0), num(1))
f(x) = max(f(x - 1), f(x - 2) + num(x)) 
f(0) = num(0)
f(1) = max(num(0), num(1))

The complexity is O(n) and the C++ source code is:

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

class Solution {
public:
    int rob(vector<int> &num) {
        int sz = num.size();
        if (sz == 0) return 0;
        if (sz == 1) return num[0];
        if (sz == 2) return max(num[0], num[1]);
        vector<int> f(sz);
        f[0] = num[0];
        f[1] = max(num[0], num[1]);
        for (int i = 2; i < sz; i ++) {
            f[i] = max(f[i - 2] + num[i], f[i - 1]);
        }
        return f[sz - 1]; // or return f.back();
    }
};
class Solution {
public:
    int rob(vector<int> &num) {
        int sz = num.size();
        if (sz == 0) return 0;
        if (sz == 1) return num[0];
        if (sz == 2) return max(num[0], num[1]);
        vector<int> f(sz);
        f[0] = num[0];
        f[1] = max(num[0], num[1]);
        for (int i = 2; i < sz; i ++) {
            f[i] = max(f[i - 2] + num[i], f[i - 1]);
        }
        return f[sz - 1]; // or return f.back();
    }
};
coding-exercise-house-robber Using the Dynamic Programming Algorithm, the Depth First Search or Breadth First Search to Solve House Robber Problem (Largest Sum of Non-Adjacent Numbers) algorithms BFS Breadth First Search c / c++ Depth First Search DFS dynamic programming Dynamic Programming Memoization python Recursion

coding-exercise-house-robber

If you solve this, you can similarly solve the following variations of the problem using Dynamic Programming Algorithm.

Let’s take another look at above DP implementation – which uses O(N) space. We don’t need to store the intermediate F values in the result, instead, we can use two variables (similar to Fibonacci numbers) to store the previous two items along the process and update them accordingly. Since this is the bottom-up approach, we will finish computing the n, n+1 items before we move to n+2, n+3 items.

Thus, the O(1) space optimisation for the above Dynamic Programming algorithm is:

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

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];
        if (nums.size() == 2) return max(nums[0], nums[1]);        
        int f0 = nums[0];
        int f1 = max(nums[0], nums[1]);
        for (int i = 2; i < nums.size(); ++ i) {
            int t = max(nums[i] + f0, f1);
            f0 = f1;
            f1 = t;
        }
        return f1;
    }
};
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];
        if (nums.size() == 2) return max(nums[0], nums[1]);        
        int f0 = nums[0];
        int f1 = max(nums[0], nums[1]);
        for (int i = 2; i < nums.size(); ++ i) {
            int t = max(nums[i] + f0, f1);
            f0 = f1;
            f1 = t;
        }
        return f1;
    }
};

We can actually implement directly the DP equation using Recursion:

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

class Solution {
public:
    int rob(vector<int>& nums) {
        return dp(nums, nums.size() - 1);
    }
 
private:
    int dp(vector<int>& nums, int n) {
        if (nums.empty()) return 0;
        if (n == 0) return nums[0];
        if (n == 1) return max(nums[0], nums[1]);
        return max(nums[n] + dp(nums, n - 2), dp(nums, n - 1));
    }
};
class Solution {
public:
    int rob(vector<int>& nums) {
        return dp(nums, nums.size() - 1);
    }

private:
    int dp(vector<int>& nums, int n) {
        if (nums.empty()) return 0;
        if (n == 0) return nums[0];
        if (n == 1) return max(nums[0], nums[1]);
        return max(nums[n] + dp(nums, n - 2), dp(nums, n - 1));
    }
};

However, as the intermediate values are computed over and over again, the above time complexity is actually exponential. We can optimise this and fix it by using a hash map table to remember the values we have already calculated – which is also known as the memoization techniques.

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

class Solution {
public:
    int rob(vector<int>& nums) {
        return dp(nums, nums.size() - 1);
    }
private:
    unordered_map<int, int> memo;
    int dp(vector<int>& nums, int n) {
        if (nums.empty()) return 0;
        if (n == 0) return nums[0];
        if (n == 1) return max(nums[0], nums[1]);
        if (memo.find(n) != memo.end()) return memo[n];
        auto ans = max(nums[n] + dp(nums, n - 2), dp(nums, n - 1));
        return memo[n] = ans;        
    }
};
class Solution {
public:
    int rob(vector<int>& nums) {
        return dp(nums, nums.size() - 1);
    }
private:
    unordered_map<int, int> memo;
    int dp(vector<int>& nums, int n) {
        if (nums.empty()) return 0;
        if (n == 0) return nums[0];
        if (n == 1) return max(nums[0], nums[1]);
        if (memo.find(n) != memo.end()) return memo[n];
        auto ans = max(nums[n] + dp(nums, n - 2), dp(nums, n - 1));
        return memo[n] = ans;        
    }
};

This solution uses O(N) space (the explicit usage of a hash map) – and O(N) time.

In Python3, we can use the @lru_cache or @cache from the funtools (High-order functions and operations to callable objects) to simplify this by one function attribute:

Top Down Dynamic Programming Algorithm via Recursion with Memoziation:

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

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

Max/Largest Sum of Non-Adjacent Numbers via Recursive DFS or BFS Algorithm

We can also use the Depth First Search or Breadth First Search algorithm to perform the search from left to right (whereas the Dynamic Programming solves the problem from right to left by remembering the answers to sub problems).

The Depth first search and Breadth First Search algorithm however are inefficient as the following implementations compute the intermediate results over and over again.

The Breadth first Serch implemented using C++ with the queue:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int rob(vector<int>& nums) {        
        if (nums.empty()) return 0;
        queue<tuple<bool, int, int>> Q;
        Q.push(make_tuple(false, -1, 0));
        int ans = 0;
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            bool taken = std::get<0>(p);
            int idx = std::get<1>(p);            
            int total = std::get<2>(p);
            ans = max(ans, total);
            if (idx + 1 < nums.size()) {                
                Q.push(make_tuple(false, idx + 1, total));
                if (!taken) {
                    Q.push(make_tuple(true, idx + 1, total + nums[idx + 1]));                         
                }                
            }
        }
        return ans;
    }
};
class Solution {
public:
    int rob(vector<int>& nums) {        
        if (nums.empty()) return 0;
        queue<tuple<bool, int, int>> Q;
        Q.push(make_tuple(false, -1, 0));
        int ans = 0;
        while (!Q.empty()) {
            auto p = Q.front();
            Q.pop();
            bool taken = std::get<0>(p);
            int idx = std::get<1>(p);            
            int total = std::get<2>(p);
            ans = max(ans, total);
            if (idx + 1 < nums.size()) {                
                Q.push(make_tuple(false, idx + 1, total));
                if (!taken) {
                    Q.push(make_tuple(true, idx + 1, total + nums[idx + 1]));                         
                }                
            }
        }
        return ans;
    }
};

And the DFS algorithm implemented in C++ using Recursion:

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

class Solution {
public:
    int rob(vector<int>& nums) {        
        dfs(nums, 0, 0);
        return ans;
    }
private:
    void dfs(vector<int>& nums, int index, int total) {
        ans = max(total, ans);
        for (int i = index; i < nums.size(); ++ i) {
            total += nums[i];
            dfs(nums, i + 2, total);
            total -= nums[i];
            dfs(nums, i + 1, total);
        }
    }
    int ans = 0;
};
class Solution {
public:
    int rob(vector<int>& nums) {        
        dfs(nums, 0, 0);
        return ans;
    }
private:
    void dfs(vector<int>& nums, int index, int total) {
        ans = max(total, ans);
        for (int i = index; i < nums.size(); ++ i) {
            total += nums[i];
            dfs(nums, i + 2, total);
            total -= nums[i];
            dfs(nums, i + 1, total);
        }
    }
    int ans = 0;
};

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

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
1417 words
Last Post: SQL Coding Exercise - Delete Duplicate Emails
Next Post: Regex Coding Exercise - Valid Phone Numbers

The Permanent URL is: Using the Dynamic Programming Algorithm, the Depth First Search or Breadth First Search to Solve House Robber Problem (Largest Sum of Non-Adjacent Numbers)

Related posts:

  1. Design a Last Value Map in C++ Implement a data structure LastValueMap which has the following methods: void set(int key, int value)...
  2. Teaching Kids Programming – Form Smallest Number From Two Digit Arrays (Set Intersection) Teaching Kids Programming: Videos on Data Structures and Algorithms Given two arrays of unique digits...
  3. The USB Flash Benchmark Tool – FlashBench Previously, it is recommended that the USBCheck can be quite helpful in checking the quality...
  4. Recursive Depth First Search Algorithm to Delete Leaves With a Given Value in a Binary Tree Given a binary tree root and an integer target, delete all the leaf nodes with...
  5. Teaching Kids Programming – Number of Ways to Reach a Position After Exactly k Steps (Combinations + Math + Dynamic Programming Algorithms) Teaching Kids Programming: Videos on Data Structures and Algorithms You are given two positive integers...
  6. Depth First Search Algorithm to Check If Two Expression Trees are Equivalent A binary expression tree is a kind of binary tree used to represent arithmetic expressions....
  7. A Short Introduction – Linear Regression Algorithm linear regression is perhaps one of the most well known and well understood algorithms in...
  8. WordPress Hosting Services You Can’t DIY If you happen to be using WordPress for your website, there’s no doubt that you’re...

3 Comments

  1. neha

    how to print indexes of robbed houses??

    Reply
    • ACMer

      you can store the indices when you do the max() selection along the scan.

      Reply
  2. neha

    how to print indexes of robbed houses

    Reply

Leave a Reply