{"id":277,"date":"2020-12-20T14:55:51","date_gmt":"2020-12-20T14:55:51","guid":{"rendered":"https:\/\/www.canosielabs.com\/blog\/?p=277"},"modified":"2020-12-20T18:48:45","modified_gmt":"2020-12-20T18:48:45","slug":"house-robber","status":"publish","type":"post","link":"https:\/\/www.canosielabs.com\/blog\/house-robber\/","title":{"rendered":"House Robber"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Today, we are going to study Leetcode&#8217;s <a href=\"https:\/\/leetcode.com\/problems\/house-robber\" data-type=\"URL\" data-id=\"https:\/\/leetcode.com\/problems\/house-robber\">house robber<\/a>.    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&nbsp;<strong>without alerting the police<\/strong> (you cannot rob two adjacent homes).  Let&#8217;s list out some facts.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Fact 1: <\/strong>Working from the end of the list to index 0, at each house, you are given the choice to rob a house or not. If you choose to rob a house and get its value, you cannot rob the n-1 house.  <\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Fact 2:<\/strong> You can maximize the value obtain from the first n houses by maximizing the value obtained from the first n-1 houses (and not including the value of the n<sup>th<\/sup> house) or maximizing the value of the first n-2 house plus the value of the n<sup>th<\/sup> house.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.canosielabs.com\/blog\/wp-content\/uploads\/2020\/12\/function.png\" alt=\"\" class=\"wp-image-278\" width=\"319\" height=\"83\" srcset=\"https:\/\/www.canosielabs.com\/blog\/wp-content\/uploads\/2020\/12\/function.png 633w, https:\/\/www.canosielabs.com\/blog\/wp-content\/uploads\/2020\/12\/function-300x78.png 300w, https:\/\/www.canosielabs.com\/blog\/wp-content\/uploads\/2020\/12\/function-250x65.png 250w, https:\/\/www.canosielabs.com\/blog\/wp-content\/uploads\/2020\/12\/function-550x143.png 550w\" sizes=\"auto, (max-width: 319px) 100vw, 319px\" \/><\/figure><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">This sure sounds like a dynamic programing problem.  <\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Overlapping Sub-problem<\/strong>&nbsp;\u2013 Yes. We can see that as we break the problem down, we are repeating the subproblems multiple times.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Optimal Substructure<\/strong>&nbsp;\u2013 Yes. Fact 2 describes why finding the optimal solution to the subproblems (n-1, n-2&#8230;.) leads to the optimal solution of finding the maximum value obtainable considering all n homes.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Base case(s)<\/strong>&nbsp;\u2013 the two base cases for this solution is f(0) = value[0].<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">DP Table<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">In this problem, our cache table will simply store at index n, the maximum obtainable value of the first n homes.  <\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Memoization<\/h2>\n\n\n\n<pre><code class=\"language-java\">class Solution {\n    private int[] cache;\n    public int rob(int[] nums) {\n        if (nums.length == 0){\n            return 0;\n        }                        \n        cache = new int[nums.length];  \n        \n        \/\/ house values can be 0\n        Arrays.fill(cache, -1);\n        \n        return robHouse(nums, nums.length-1);        \n    }\n    \n    public int robHouse(int[] nums, int n) {      \n        \/\/ base case n == 0\n        if (n == 0) {            \n            return nums[0];\n        } else if (cache[n] &gt; -1) {\n            return cache[n];\n        }\n        \n        int includeNth = n-2 &gt;= 0 ? robHouse(nums, n-2) + nums[n] : nums[n];\n        int notIncludeNth = robHouse(nums, n-1);\n        \n        \n        int maxValue = includeNth &gt; notIncludeNth ? includeNth: notIncludeNth;\n        cache[n] = maxValue;   \n        return maxValue;\n    }\n}<\/code><\/pre><br><br>\n\n\n\n<h2 class=\"wp-block-heading\">Tabulation<\/h2>\n\n\n\n<pre><code class=\"language-java\">class Solution {\n    public int rob(int[] nums) {\n        if (nums.length == 0){\n            return 0;\n        }                   \n        int[] cache = new int[nums.length];    \n        cache[0] = nums[0];\n        \n        for(int i=1; i= 0 ? cache[i-2] + nums[i] : nums[i];\n            int notIncludeNth = cache[i-1];                \n            cache[i] = includeNth &gt; notIncludeNth ? includeNth: notIncludeNth;\n        }        \n        return cache[nums.length-1];      \n    }\n}<\/code><\/pre><br><br>\n\n\n\n<h2 class=\"wp-block-heading\">Conclusion<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">This is a relatively simple question, but the wording often throws some people off.  One of the difficulties candidates encounter (including myself the first time I saw this problem) was understanding what<strong> &#8220;two adjacent homes&#8221;<\/strong> means.  Given 3 homes in the order of [A, B, C]:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>It means that you cannot rob two sequential home in a row.  I.e. [A, B] or [B, C]<\/li><li>A common misconception is that you cannot rob homes A and C because B will have &#8216;two adjacent homes&#8217; that have been robbed.  <\/li><\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">This makes the problem much more difficult so if you are issuing this question, it&#8217;s important confirm that the candidate understands the reequipments clearly.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Today, we are going to study Leetcode&#8217;s house robber. Given a list of non-negative integers representing the amount of money of each house, determine the&hellip;<\/p>\n","protected":false},"author":3,"featured_media":255,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"bgseo_title":"","bgseo_description":"","bgseo_robots_index":"index","bgseo_robots_follow":"follow","footnotes":""},"categories":[11],"tags":[10],"class_list":["post-277","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-interview-coding-questions","tag-coding-questions"],"_links":{"self":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/277","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/comments?post=277"}],"version-history":[{"count":7,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/277\/revisions"}],"predecessor-version":[{"id":291,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/277\/revisions\/291"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/media\/255"}],"wp:attachment":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/media?parent=277"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/categories?post=277"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/tags?post=277"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}