006 — House Robber¶

Source¶

Original source: Classic take-or-skip DP exercise
Platform: LeetCode — https://leetcode.com/problems/house-robber/
Topic: dynamic programming
Difficulty: Medium
Pattern: 1D take-or-skip DP
Basic idea inherited from: #3 Min Cost Climbing Stairs — পেছনের দুই-ঘর সিদ্ধান্ত, কিন্তু max আর "skip one" নিয়ম

1. Problem in simple words¶

এক সারিতে কতগুলো বাড়ি, প্রত্যেকটায় কিছু টাকা — array nums। তুমি চোর, যত টাকা পারো লুটবে। কিন্তু একটা নিয়ম: পাশাপাশি দুটো বাড়ি একসাথে লুট করা যাবে না (alarm বাজবে)। সর্বোচ্চ কত টাকা লুট করতে পারবে, সেটা বের করো।

nums = [2, 7, 9, 3, 1]
সবচেয়ে ভালো: বাড়ি 0 (2) + বাড়ি 2 (9) + বাড়ি 4 (1) = 12

2. Which basic idea does this inherit from?¶

ভিত্তি #3 Min Cost Climbing Stairs-এর পেছন-দুই-ঘর সিদ্ধান্ত। সেখানে প্রতিটা position-এ দুটো আগের ঘর দেখতাম; এখানেও তাই, কিন্তু লক্ষ্য max (min নয়) আর নিয়মটা "পাশাপাশি নয়" — যা transition-এ dp[i-2]-এ হাত বাড়িয়ে enforce হয়।

3. What is the hidden math or logic?¶

লুকানো logic একটা সিদ্ধান্ত: বাড়ি i-তে দাঁড়িয়ে হয় লুট করো, নয় বাদ দাও। লুট করলে nums[i] পাও, কিন্তু বাড়ি i-1 নিষিদ্ধ হয়ে যায় — তাই তার আগে best হলো বাড়ি 0..i-2-এর best। বাদ দিলে best অপরিবর্তিত — বাড়ি 0..i-1-এর best। এই দুটোর max-ই উত্তর।

4. Which data structure is needed?¶

একটা array dp (size n), dp[i] = বাড়ি 0..i থেকে সম্ভব max লুট। অথবা শুধু দুটো variable, কারণ dp[i] শুধু dp[i-1] আর dp[i-2] পড়ে।

5. Why this data structure fits¶

State একটামাত্র সংখ্যা: কত নম্বর বাড়ি পর্যন্ত বিবেচনা করেছি। তাই index দিয়ে চলা flat array নিখুঁত — dp[i] প্রথম i+1 বাড়ির best লুট ধরে। Dependency পেছনের দুই ঘরে, তাই পুরো array না রেখে দুই rolling variable-এ চলে।

6. Real-life analogy¶

ভাবো রাস্তার পাশে সারি বাড়ি, আর তুমি হাঁটতে হাঁটতে ঠিক করছ কোনগুলো "ছোঁবে"। প্রতিটা বাড়ির সামনে দাঁড়িয়ে দুটো হিসাব করো: "এটা ছুঁলে — তাহলে আগেরটা বাদ, মানে দুই বাড়ি আগের পর্যন্ত আমার সেরা + এই বাড়ির টাকা" আর "এটা না ছুঁলে — তাহলে আগের বাড়ি পর্যন্ত আমার সেরা।" বড়টা বেছে এগোও।

7. Visual explanation¶

dp[i] = বাড়ি 0..i-এর max লুট। nums = [2, 7, 9, 3, 1]:

i     :   0    1    2    3    4
nums  :   2    7    9    3    1

dp[i] = max( dp[i-1],            # skip house i
             dp[i-2] + nums[i] )  # rob house i

dp[0] = 2
dp[1] = max(2, 7)           = 7
dp[2] = max(dp[1], dp[0]+9) = max(7, 2+9)  = 11
dp[3] = max(dp[2], dp[1]+3) = max(11, 7+3) = 11
dp[4] = max(dp[3], dp[2]+1) = max(11, 11+1)= 12   <- answer

dp    :   2    7   11   11   12

প্রতিটা ঘর: পাশেরটা skip করে আগের best, নাকি এটা rob করে দুই-আগের best + টাকা — যেটা বড়।

8. Example input and output¶

Input : nums = [2, 7, 9, 3, 1]  -> Output: 12   (2 + 9 + 1)
Input : nums = [1, 2, 3, 1]     -> Output: 4    (1 + 3)
Input : nums = [2, 1, 1, 2]     -> Output: 4    (2 + 2)

Edge case 1: nums = [5]      -> Output: 5
Edge case 2: nums = [2, 3]   -> Output: 3   (পাশাপাশি, তাই বড়টা)

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা বাড়ির জন্য recurse করে দুটো শাখা দেখা — rob করো (দুই ধাপ লাফাও) বা skip করো (এক ধাপ)।

rob(i):                          # বাড়ি 0..i থেকে best লুট
    if i < 0: return 0
    return max( rob(i-1),         # skip
                rob(i-2) + nums[i] )  # rob
answer = rob(n-1)

10. Why brute force is slow¶

এই recursion O(2^n) — প্রতিটা বাড়িতে দুটো শাখা, আর একই index বারবার গোনা হয় (overlapping subproblems)। rob(i-1) আর rob(i-2) দুজনেই নিচে গিয়ে আবার একই subproblem ছোঁয়। 30+ বাড়ি হলেই এটা খুব ধীর।

11. Key observation¶

মূল observation: প্রতিটা বাড়ি পর্যন্ত best লুট একবারই গোনা দরকার, কারণ সেটা শুধু পেছনের দুই বাড়ির best-এর উপর নির্ভর করে। একবার গুনে রাখলে exponential কাজ linear হয়ে যায়।

12. Optimized intuition¶

State (শব্দে): dp[i] = প্রথম i+1-টা বাড়ি (বাড়ি 0..i) থেকে সম্ভব maximum লুট — বাড়ি i নিজে লুট হয়েছে কি না, তার শর্ত ছাড়াই।

Transition:

dp[i] = max( dp[i-1],            # skip house i
             dp[i-2] + nums[i] )  # rob it -> i-1 নিষিদ্ধ

কারণ: বাড়ি i লুট করলে তার আগে best হলো বাড়ি 0..i-2-এর best; "no adjacent" নিয়মটা কোন ছোট state-এ হাত বাড়াচ্ছি তা দিয়েই enforce হয়।

Base case: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])।

Answer location: dp[n-1]।

Memoization (top-down): উপরের rob(i) recursion-টাই রাখো, dict যোগ করো। Tabulation (bottom-up): দুই base থেকে শুরু করে বাঁ-থেকে-ডান ভরো। Dependency দুই ঘরে, তাই দুই variable rolling করে O(1) space।

13. Thinking tweak¶

মোচড়: "কোন বাড়িগুলো লুট করব" — এই subset খোঁজার বদলে প্রতিটা বাড়িতে শুধু একটা লোকাল প্রশ্ন করো: "এটা rob, না skip?" নিয়মটা (পাশাপাশি নয়) এমনিতেই মেনে যায়, কারণ rob করলে আমরা i-2-এ লাফ দিই — পাশের বাড়িটা এড়িয়ে। বড় সিদ্ধান্ত ছোট binary choice-এ ভেঙে যায়।

14. Step-by-step dry run¶

nums = [2, 1, 1, 2], O(1) version (a = dp[i-2], b = dp[i-1]):

dp[0] = 2, dp[1] = max(2, 1) = 2; তাই a = 2, b = 2
i=2: cur = max(b, a + nums[2]) = max(2, 2+1) = 3; a, b = 2, 3
i=3: cur = max(b, a + nums[3]) = max(3, 2+2) = 4; a, b = 3, 4
return b = 4

হাতে মিলিয়ে: বাড়ি 0 (2) + বাড়ি 3 (2) = 4। ✔

15. Python solution¶

# ---- way 1: memoization (top-down) ----
def rob_memo(nums):
    memo = {}
    def solve(i):                            # বাড়ি 0..i থেকে best লুট
        if i < 0:
            return 0
        if i == 0:
            return nums[0]
        if i in memo:
            return memo[i]
        memo[i] = max(solve(i - 1),          # skip
                      solve(i - 2) + nums[i]) # rob
        return memo[i]
    return solve(len(nums) - 1)

# ---- way 2: tabulation (bottom-up) ----
def rob_tab(nums):
    n = len(nums)
    if n == 1:
        return nums[0]
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    return dp[n - 1]

# ---- way 3: O(1) space ----
def rob_fast(nums):
    a, b = 0, 0                              # best for 0..i-2, 0..i-1
    for x in nums:
        a, b = b, max(b, a + x)             # rob x -> a + x; skip -> b
    return b

# ---- tests ----
cases = [
    ([2, 7, 9, 3, 1], 12),
    ([1, 2, 3, 1], 4),
    ([2, 1, 1, 2], 4),
    ([5], 5),
    ([2, 3], 3),
    ([0], 0),
    ([100, 1, 1, 100], 200),
]
for nums, want in cases:
    assert rob_memo(nums) == want, (nums, rob_memo(nums))
    assert rob_tab(nums) == want, (nums, rob_tab(nums))
    assert rob_fast(nums) == want, (nums, rob_fast(nums))

print("সব test pass!")

16. Line-by-line code explanation¶

rob_memo: ভেতরের solve(i) বাড়ি 0..i-এর best লুট দেয়; i < 0 → 0, i == 0 → nums[0]; memo repeated কাজ এড়ায়।
rob_tab: একটা বাড়ি হলে আলাদা; নয়তো দুই base, তারপর loop প্রতি বাড়িতে rob-vs-skip max নেয়; answer dp[n-1]।
rob_fast: a = দুই-আগের best, b = আগের best; a, b = b, max(b, a + x) এক assignment-এই এগোয়, পুরো array ছাড়া।

17. Output walkthrough¶

cases-এ সাতটা input: তিনটা classic, single house, পাশাপাশি জোড়া, একটা শূন্য, আর একটা "প্রান্ত-দুটো" trap ([100,1,1,100] → 200, মানে greedy "সবচেয়ে বড় আগে" এখানেও ঠিক হয় কিন্তু সাধারণভাবে নয়)। প্রতিটার জন্য তিন function-ই মিলতে হবে। সব pass হলে শেষে print: সব test pass!।

18. Time complexity¶

তিন version-ই O(n) — প্রতিটা বাড়ি একবার করে বিবেচনা হয়। (Naive recursion ছিল O(2^n)।)

19. Space complexity¶

Memoization: O(n) — dict + recursion stack।
Tabulation: O(n) — dp array।
Fast version: O(1) — দুটো variable।

20. Common mistakes¶

dp[1] কে nums[1] ভাবা max(nums[0], nums[1])-এর বদলে — প্রথম দুই বাড়ির মধ্যে বড়টা নিতে হয়।
rob করার সময় dp[i-1] + nums[i] লেখা (dp[i-2]-এর বদলে) — তখন পাশের বাড়িও লুট হয়ে যায়, নিয়ম ভাঙে।
single-house array আলাদা না ভাবা — তখন tabulation-এ dp[1] index error দেয়।

21. Which basic problem this inherits from¶

ভিত্তি: #3 Min Cost Climbing Stairs-এর পেছন-দুই-ঘর সিদ্ধান্ত, min-কে max আর "skip one" দিয়ে বদলানো। ../state-transition-thinking.md-এর "Problem 2 — House Robber" section-এ ঠিক এই state-design (choice-কে transition-এ fold করা) বিস্তারিত আছে।

22. Similar harder problems¶

House Robber II (বাড়িগুলো বৃত্তে, প্রথম-শেষ adjacent) — LeetCode "House Robber II" at https://leetcode.com/ (এই tracker-এর #20)
House Robber III (বাড়িগুলো গাছে) — https://leetcode.com/problems/house-robber-iii/
Delete and Earn (একই take-or-skip, value বানিয়ে) — https://leetcode.com/problems/delete-and-earn/

23. Pattern learned¶

Take-or-skip DP: প্রতিটা element-এ binary সিদ্ধান্ত (নাও/বাদ দাও), আর "নিলে কোন আগের state-এ লাফ দিই" তা দিয়ে constraint enforce করো। dp[i] = max(skip, take + dp[i-2]) — এই কঙ্কাল বহু selection problem-এ ফেরে।

24. Final summary¶

ভবিষ্যতের আমাকে: "House Robber = take-or-skip DP।" State 'বাড়ি 0..i-এর best লুট', transition dp[i] = max(dp[i-1], dp[i-2]+nums[i]), base দুটো। মনে রেখো: constraint ("পাশাপাশি নয়") state-এ নয়, transition-এর লাফেই বসানো — i-2-এ হাত বাড়িয়ে। এই reflex অনেক DP-তে কাজে লাগবে।

25. JavaScript solution (with test cases)¶

Take-or-skip DP; O(1) version-এ a, b = b, max(b, a + x)। Math.max Python-এর max-এর সমতুল্য।

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// dp array version
function robTab(nums) {
  const n = nums.length;
  if (n === 1) return nums[0];
  const dp = new Array(n).fill(0);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < n; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);   // skip নাকি rob
  }
  return dp[n - 1];
}
// O(1) space: a = dp[i-2], b = dp[i-1]
function robFast(nums) {
  let a = 0, b = 0;                          // best for 0..i-2, 0..i-1
  for (const x of nums) {
    [a, b] = [b, Math.max(b, a + x)];        // rob x -> a+x; skip -> b
  }
  return b;
}
// ---- test cases (example + edge) ----
const cases = [
  [[2, 7, 9, 3, 1], 12],
  [[1, 2, 3, 1], 4],
  [[2, 1, 1, 2], 4],
  [[5], 5],                                  // single house
  [[2, 3], 3],                               // adjacent pair edge
  [[0], 0],
  [[100, 1, 1, 100], 200],
];
for (const [nums, want] of cases) {
  assert(robTab(nums) === want, "tab " + nums);
  assert(robFast(nums) === want, "fast " + nums);
}
console.log("সব JS test pass!");

JS টীকা: O(1) version-এ [a, b] = [b, Math.max(b, a + x)] — destructuring assignment দিয়ে দুটো variable একসাথে update হয়, তাই Python-এর a, b = b, max(...)-এর মতো temp লাগে না। new Array(n).fill(0) দিয়ে number array নিরাপদ (primitive); base dp[1] = Math.max(nums[0], nums[1]), single-house আলাদা handle না করলে dp[1] index undefined হতো।

26. TypeScript solution (with test cases)¶

function robFast(nums: number[]): number {
  if (nums.length === 0) return 0;
  let a = 0, b = 0;                          // best for 0..i-2, 0..i-1
  for (const x of nums) {
    [a, b] = [b, Math.max(b, a + x)];
  }
  return b;
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
const cases: Array<[number[], number]> = [
  [[2, 7, 9, 3, 1], 12],
  [[1, 2, 3, 1], 4],
  [[2, 1, 1, 2], 4],
  [[5], 5],
  [[2, 3], 3],
  [[100, 1, 1, 100], 200],
];
for (const [nums, want] of cases) expect(robFast(nums), want, "rob " + nums);
console.log("সব TS test pass!");

TS টীকা: parameter number[] declare করায় ভুলে string array পাঠালে compile-error; cases: Array<[number[], number]> tuple-type দিয়ে প্রতিটা test যে ঠিক [array, expected] জোড়া তা locked, তাই destructure-এ nums: number[], want: number আপনাআপনি।

27. কোথায় কাজে লাগে (real-world use)¶

Resource selection with adjacency constraint: এমন item বাছা যেখানে পাশাপাশি দুটো একসাথে নেওয়া নিষেধ (পরস্পর-বিরোধী slot), মোট value সর্বোচ্চ করে।
Scheduling non-adjacent jobs: সময়-সারিতে এমন কাজ বাছা যেন পাশাপাশি দুটো overlap না করে, মোট লাভ সর্বোচ্চ।
Ad / placement selection: পাশাপাশি না বসিয়ে সর্বোচ্চ revenue-এর বিজ্ঞাপন বাছা।
Sensor / node activation: শক্তি বাঁচাতে পাশাপাশি sensor একসাথে না জ্বালিয়ে coverage/মান সর্বোচ্চ করা।
Telecom channel allocation: interference এড়াতে পাশাপাশি channel না নিয়ে মোট throughput সর্বোচ্চ।

মূল pattern: প্রতিটা element-এ "নাও নাকি skip", আর "নিলে কোন আগের state-এ লাফ" দিয়ে constraint enforce — dp[i] = max(skip, take + dp[i-2])।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।