Problem link ও উৎস
- **Original source:** Classic take-or-skip DP exercise
- **Platform:** LeetCode —
- **Topic:** dynamic programming
- **Difficulty:** Medium
- **Pattern:** 1D take-or-skip DP
- **Basic idea inherited from:** #3 Min Cost Climbing Stairs — পেছনের দুই-ঘর সিদ্ধান্ত, কিন্তু max আর "skip one" নিয়ম
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
এক সারিতে কতগুলো বাড়ি, প্রত্যেকটায় কিছু টাকা — array `nums`। তুমি চোর, যত টাকা পারো লুটবে। কিন্তু একটা নিয়ম: **পাশাপাশি দুটো বাড়ি একসাথে লুট করা যাবে না** (alarm বাজবে)। সর্বোচ্চ কত টাকা লুট করতে পারবে, সেটা বের করো।
```text
nums = [2, 7, 9, 3, 1]
সবচেয়ে ভালো: বাড়ি 0 (2) + বাড়ি 2 (9) + বাড়ি 4 (1) = 12
```
### Input ও output {#8-example-input-and-output}
```text
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 (পাশাপাশি, তাই বড়টা)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো রাস্তার পাশে সারি বাড়ি, আর তুমি হাঁটতে হাঁটতে ঠিক করছ কোনগুলো "ছোঁবে"। প্রতিটা বাড়ির সামনে দাঁড়িয়ে দুটো হিসাব করো: "এটা ছুঁলে — তাহলে আগেরটা বাদ, মানে দুই বাড়ি আগের পর্যন্ত আমার সেরা + এই বাড়ির টাকা" আর "এটা না ছুঁলে — তাহলে আগের বাড়ি পর্যন্ত আমার সেরা।" বড়টা বেছে এগোও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এ চলে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা বাড়ির জন্য recurse করে দুটো শাখা দেখা — rob করো (দুই ধাপ লাফাও) বা skip করো (এক ধাপ)।
```text
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:**
```text
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-এ ভেঙে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`dp[i]` = বাড়ি `0..i`-এর max লুট। `nums = [2, 7, 9, 3, 1]`:
```text
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 + টাকা — যেটা বড়।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`nums = [2, 1, 1, 2]`, O(1) version (`a` = `dp[i-2]`, `b` = `dp[i-1]`):
1. `dp[0] = 2`, `dp[1] = max(2, 1) = 2`; তাই `a = 2`, `b = 2`
2. i=2: `cur = max(b, a + nums[2]) = max(2, 2+1) = 3`; `a, b = 2, 3`
3. i=3: `cur = max(b, a + nums[3]) = max(3, 2+2) = 4`; `a, b = 3, 4`
4. return `b = 4`
হাতে মিলিয়ে: বাড়ি 0 (2) + বাড়ি 3 (2) = 4। ✔
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
# ---- 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 ছাড়া।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ সাতটা input: তিনটা classic, single house, পাশাপাশি জোড়া, একটা শূন্য, আর একটা "প্রান্ত-দুটো" trap (`[100,1,1,100]` → 200, মানে greedy "সবচেয়ে বড় আগে" এখানেও ঠিক হয় কিন্তু সাধারণভাবে নয়)। প্রতিটার জন্য তিন function-ই মিলতে হবে। সব pass হলে শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
Take-or-skip DP; O(1) version-এ `a, b = b, max(b, a + x)`। `Math.max` Python-এর `max`-এর সমতুল্য।
```javascript
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 হতো।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
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