https://vprog.hu/_app/immutable/nodes/8.naNPtlAc.js

1import"../chunks/DsnmJJEf.js";import"../chunks/-EMG-SoD.js";import{p,b as i}from"../chunks/fM471mxQ.js";import{i as t}from"../chunks/oqioA-Uj.js";import{P as o}from"../chunks/DdeOd1HT.js";import{p as c}from"../chunks/cHDGrtPc.js";const r=`<p>You are a professional robber planning to rob houses along a street.
2Each house has a certain amount of money stashed, the only constraint
3stopping you from robbing each of them is that adjacent houses have
4security systems connected and it will automatically contact the police
5if two adjacent houses were broken into on the same night.</p>
6<p>Given an integer array nums representing the amount of money of each
7house, return the maximum amount of money you can rob tonight without
8alerting the police.</p>
9<p>Usually the first approach I see people come up with for this
10exercise goes something along the lines of: “let’s iterate the house
11array</p>
12<p>You might try solving it with a heuristic, but there will be
13counterexamples to all of them. Heuristics are solutions where you
14always make a decision based on local information as you iterate your
15nums array.</p>
16<p>The problem is that when we make a decision whether to rob a house or
17not, it can never be undone later, if we find something better along the
18way. If we include a new house into the robbed ones, suddenly its
19neighbour cannot be included, so maybe the previous neighbour should be,
20and so on, the change might bubble up all the way to the beginning… how
21do we deal with these in an organized manner?</p>
22<p>Instead of sticking to a choice, check what happens in both cases! So
23for instance, we can either include the last house or not.</p>
24<p>If we include the n’th house, then obviously the n-1’th cannot be
25included… what we are left with is solving the same problem… for houses
261 .. n-2! And if we don’t include the n’th house … well then we must
27solve the problem for houses 1 .. n-1!</p>
28<p>So if we have a solver for between 1 .. n , maybe call it solve(n),
29this will be a recursive function, like so:</p>
30<div class="sourceCode" id="cb1"><pre
31class="sourceCode python"><code class="sourceCode python"><span id="cb1-1"><a href="#cb1-1" aria-hidden="true" tabindex="-1"></a>nums <span class="op">=</span> [<span class="dv">0</span>] <span class="op">+</span> nums <span class="co"># Let&#39;s index houses from 1 to n, for better readability.</span></span>
32<span id="cb1-2"><a href="#cb1-2" aria-hidden="true" tabindex="-1"></a><span class="kw">def</span> solver(i): <span class="co"># Solve or 1..i.</span></span>
33<span id="cb1-3"><a href="#cb1-3" aria-hidden="true" tabindex="-1"></a>  <span class="co"># Base cases</span></span>
34<span id="cb1-4"><a href="#cb1-4" aria-hidden="true" tabindex="-1"></a>  <span class="cf">if</span> i<span class="op">==</span><span class="dv">0</span>: <span class="co"># If we have no houses, we can rob 0 money.</span></span>
35<span id="cb1-5"><a href="#cb1-5" aria-hidden="true" tabindex="-1"></a>    <span class="cf">return</span> <span class="dv">0</span></span>
36<span id="cb1-6"><a href="#cb1-6" aria-hidden="true" tabindex="-1"></a>  <span class="cf">if</span> i<span class="op">==</span><span class="dv">1</span>: <span class="co"># We can only rob the first house, so let&#39;s do it!</span></span>
37<span id="cb1-7"><a href="#cb1-7" aria-hidden="true" tabindex="-1"></a>    <span class="cf">return</span> nums[<span class="dv">1</span>]</span>
38<span id="cb1-8"><a href="#cb1-8" aria-hidden="true" tabindex="-1"></a>  <span class="cf">return</span> <span class="bu">max</span>(solver(i<span class="op">-</span><span class="dv">2</span>) <span class="op">+</span> nums[i], solver(i<span class="op">-</span><span class="dv">1</span>))</span>
39<span id="cb1-9"><a href="#cb1-9" aria-hidden="true" tabindex="-1"></a></span>
40<span id="cb1-10"><a href="#cb1-10" aria-hidden="true" tabindex="-1"></a><span class="bu">print</span>(solve(n))</span></code></pre></div>
41<p>But this is not too efficient. We call solver with n, then n-1 and
42n-2; the n-1 call will call for n-2 and n-3; the n-2 call will call for
43n-3 and n-4 … lots of redundancy there. If we know a solution to an 

43n,
44we should just remember it.</p>
45<p>This is called memoization, the typo is intentional. Python can do it
46built-in, with the macro <code>@cache</code>, but let’s do it by hand
47now.</p>
48<div class="sourceCode" id="cb2"><pre
49class="sourceCode python"><code class="sourceCode python"><span id="cb2-1"><a href="#cb2-1" aria-hidden="true" tabindex="-1"></a>nums <span class="op">=</span> [<span class="dv">0</span>] <span class="op">+</span> nums <span class="co"># Let&#39;s index houses from 1 to n, for better readability.</span></span>
50<span id="cb2-2"><a href="#cb2-2" aria-hidden="true" tabindex="-1"></a>dp <span class="op">=</span> [<span class="op">-</span><span class="dv">1</span>]<span class="op">*</span><span class="bu">len</span>(nums)</span>
51<span id="cb2-3"><a href="#cb2-3" aria-hidden="true" tabindex="-1"></a></span>
52<span id="cb2-4"><a href="#cb2-4" aria-hidden="true" tabindex="-1"></a><span class="kw">def</span> solver(i): <span class="co"># Solve or 1..i.</span></span>
53<span id="cb2-5"><a href="#cb2-5" aria-hidden="true" tabindex="-1"></a>  <span class="cf">if</span> dp[i] <span class="op">!=</span> <span class="op">-</span><span class="dv">1</span>: <span class="co"># If we already solved this case, return the solution.</span></span>
54<span id="cb2-6"><a href="#cb2-6" aria-hidden="true" tabindex="-1"></a>    <span class="cf">return</span> dp[i]</span>
55<span id="cb2-7"><a href="#cb2-7" aria-hidden="true" tabindex="-1"></a></span>
56<span id="cb2-8"><a href="#cb2-8" aria-hidden="true" tabindex="-1"></a>  <span class="co"># Base cases</span></span>
57<span id="cb2-9"><a href="#cb2-9" aria-hidden="true" tabindex="-1"></a>  <span class="cf">if</span> i<span class="op">==</span><span class="dv">0</span>: <span class="co"># If we have no houses, we can rob 0 money.</span></span>
58<span id="cb2-10"><a href="#cb2-10" aria-hidden="true" tabindex="-1"></a>    dp[<span class="dv">0</span>] <span class="op">=</span> <span class="dv">0</span></span>
59<span id="cb2-11"><a href="#cb2-11" aria-hidden="true" tabindex="-1"></a>  <span class="cf">elif</span> i<span class="op">==</span><span class="dv">1</span>: <span class="co"># We can only rob the first house, so let&#39;s do it!</span></span>
60<span id="cb2-12"><a href="#cb2-12" aria-hidden="true" tabindex="-1"></a>    dp[<span class="dv">1</span>] <span class="op">=</span> nums[<span class="dv">1</span>]</span>
61<span id="cb2-13"><a href="#cb2-13" aria-hidden="true" tabindex="-1"></a>  <span class="co"># Generic case</span></span>
62<span id="cb2-14"><a href="#cb2-14" aria-hidden="true" tabindex="-1"></a>  <span class="cf">else</span>:</span>
63<span id="cb2-15"><a href="#cb2-15" aria-hidden="true" tabindex="-1"></a>    dp[i] <span class="op">=</span> <span class="bu">max</span>(solver(i<span class="op">-</span><span class="dv">2</span>) <span class="op">+</span> nums[i], solver(i<span class="op">-</span><span class="dv">1</span>))</span>
64<span id="cb2-16"><a href="#cb2-16" aria-hidden="true" tabindex="-1"></a></span>
65<span id="cb2-17"><a href="#cb2-17" aria-hidden="true" tabindex="-1"></a>  <span class="cf">return</span> dp[i]</span>
66<span id="cb2-18"><a href="#cb2-18" aria-hidden="true" tabindex="-1"></a></span>
67<span id="cb2-19"><a href="#cb2-19" aria-hidden="true" tabindex="-1"></a><span class="bu">print</span>(solve(n))</span></code></pre></div>
68<p>And at this point you can see that we’re using the recursion
69completely unnecessarily, we could just fill out that dp array from left
70to right :)</p>
71<div class="sourceCode" id="cb3"><pre
72class="sourceCode python"><code class="sourceCode python"><span id="cb3-1"><a href="#cb3-1" aria-hidden="true" tabindex="-1"></a>nums <span class="op">=</span> [<span class="dv">0</span>] <span class="op">+</span> nums <span class="co"># Let&#39;s index houses from 1 to n, for better readability.</span></span>
73<span id="cb3-2"><a href="#cb3-2" aria-hidden="true" tabindex="-1"></a>dp <span class="op">=</span> [<span class="op">-</span><span class="dv">1</span>]<span class="op">*</span><span class="bu">len</span>(nums)</span>
74<span id="cb3-3"><a href="#cb3-3" aria-hidden="true" tabindex="-1"></a></span>
75<span id="cb3-4"><a href="#cb3-4" aria-hidden="true" tabindex="-1"></a>dp[<span class="dv">0</span>] <span class="op">=</span> <span class="dv">0</span></span>
76<span id="cb3-5"><a href="#cb3-5" aria-hidden="true" tabindex="-1"></a>dp[<span class="dv">1</span>] <span class="op">=</span> nums[<span class="dv">1</span>]</span>
77<span id="cb3-6"><a href="#cb3-6" aria-hidden="true" tabindex="-1"></a></span>
78<span id="cb3-7"><a href="#cb3-7" aria-hidden="true" tabindex="-1"></a><span class="cf">for</span> i <span class="kw">in</span> <span class="bu">range</span>(<span class="dv">2</span>,n<span class="op">+</span><span class="dv">1</span>):</span>
79<span id="cb3-8"><a href="#cb3-8" aria-hidden="true" tabindex="-1"></a>  dp[i] <span class="op">=</span> <span class="bu">max</span>(dp[i<span class="op">-</span><span class="dv">2</span>] <span class="op">+</span> nums[i], dp[i<span class="op">-</span><span class="dv">1</span>])</span>
80<span id="cb3-9"><a href="#cb3-9" aria-hidden="true" tabindex="-1"></a></span>
81<span id="cb3-10"><a href="#cb3-10" aria-hidden="true" tabindex="-1"></a><span class="bu">print</span>(dp[n])</span></code></pre></div>
82<p>And this is what we call dynamic programming!</p>
83<p>We relied on the principle of optimality, which means that an optimal
84solution to the problem for 1..n can be constructed from other
85<strong>optimal solutions</strong> to subproblems, 1..n-2 and 1..n-1 !
86This is not true for all problems, consider finding a Hamiltonian path …
87you can’t just solve the problem for a subgraph, then try to build from
88there… maybe your edges have to be completely rearranged when a new
89vertex is added.</p>
90<p>This is such a powerful tool, because using the principle of
91optimality you can turn a naive 2^n solution (checking all subsets of
92houses and finding the maximum value that satisfies the constraint) into
93a linear one, since the value of the optimal subet from 1..n comes from
94the values of other <strong>optimal subsets</strong> from 1..n-1 and
951..n-2 .</p>
96<p>F.Y.I. Hamiltonian path can be solved with something called bitset
97dynamic programming, but that still has an exponential runtime and is a
98bit more trickier than this type of DP.</p>
99
100`;function m(a,n){p(n,!1);const s=c.find(e=>e.slug==="2024-03-08-house-robbery");t(),o(a,{get post(){return s},get content(){return r}}),i()}export{m as component};