Problem link ও উৎস
- **Original source:** Classic take-or-skip DP exercise, circular variant
- **Platform:** [LeetCode · House Robber II](https://leetcode.com/problems/house-robber-ii/)
- **Topic:** dynamic programming (1D + case split)
- **Difficulty:** Hard
- **Pattern:** 1D take-or-skip DP + case split
- **Basic idea inherited from:** #6 House Robber — একই take-or-skip core, কিন্তু বাড়িগুলো বৃত্তে বলে প্রথম আর শেষ বাড়ি adjacent; trick হলো linear robber-টা **দুবার** চালানো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
#6-এর মতোই বাড়ির array `nums`, প্রত্যেকটায় কিছু টাকা, পাশাপাশি দুটো লুট করা যাবে না। কিন্তু এবার বাড়িগুলো **বৃত্তে** সাজানো — মানে প্রথম বাড়ি (index 0) আর শেষ বাড়ি (index n-1) **একে অপরের পাশে**, তাই দুটো একসাথে লুট করা যাবে না। সর্বোচ্চ কত টাকা লুট করতে পারবে?
```text
nums = [2, 3, 2] (বৃত্তে: 2 - 3 - 2 - আবার 2-তে ফেরে)
বাড়ি 0 আর 2 দুটোই 2, কিন্তু adjacent (বৃত্ত), তাই একসাথে নয়।
সবচেয়ে ভালো: শুধু বাড়ি 1 (3) -> 3
```
### Input ও output {#8-example-input-and-output}
```text
Input : nums = [2, 3, 2] -> Output: 3 (শুধু 3; 0 আর 2 adjacent)
Input : nums = [1, 2, 3, 1] -> Output: 4 (1 + 3)
Input : nums = [2, 7, 9, 3, 1] -> Output: 11 (2 + 9)
Edge case 1: nums = [5] -> Output: 5 (এক বাড়ি)
Edge case 2: nums = [2, 3] -> Output: 3 (দুই বাড়ি, বড়টা)
Edge case 3: nums = [1, 2, 3] -> Output: 3 (0,2 adjacent -> মাঝেরটা বা একটা প্রান্ত)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো বাড়িগুলো একটা গোল মাঠের ধার ঘিরে। তুমি জানো প্রথম বাড়ি ছুঁলে শেষ বাড়ি ছোঁয়া যাবে না (ওরা পাশাপাশি)। তাই দুটো পরিকল্পনা করো: পরিকল্পনা A — "আমি প্রথম বাড়ি ছুঁতে পারি বলে ধরি, তাই শেষ বাড়িটা পরিকল্পনা থেকে কেটে দিই"; পরিকল্পনা B — "আমি প্রথম বাড়ি ছুঁব না, তাই শেষ বাড়ি খোলা রাখি, কিন্তু প্রথমটা কেটে দিই।" দুটো সরল সারি-লুটের হিসাব কষে বড়টা বেছে নাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি সরাসরি #6 House Robber-এর take-or-skip core: `dp[i] = max(dp[i-1], dp[i-2] + nums[i])`। নতুন জিনিস শুধু একটা constraint — প্রথম আর শেষ বাড়ি adjacent। মূল চালাকি: বৃত্তটাকে দুটো লাইনে কাটো — একটায় শেষ বাড়ি বাদ, আরেকটায় প্রথম বাড়ি বাদ — তাহলে প্রতিবার #6-এর সাধারণ linear robber-ই চালানো যায়, আর দুটোর max নিলেই উত্তর।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা সরল case split: optimal solution-এ হয় **বাড়ি 0 লুট হয়েছে, নয় হয়নি** — দুটো একসাথে নয়, এবং অন্তত একটা সত্যি। বাড়ি 0 লুট হলে বাড়ি n-1 নিষিদ্ধ; তাই `nums[0..n-2]`-এর উপর সাধারণ linear robber চালাও। বাড়ি 0 না হলে n-1 মুক্ত; তাই `nums[1..n-1]`-এর উপর চালাও। দুটোর max-ই গোটা বৃত্তের উত্তর — কারণ প্রতিটা case থেকে "0 আর n-1 একসাথে" সম্ভাবনাটা বাদ পড়েছে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কিছুই নতুন নয় — #6-এর linear robber-ই lএকটা helper function হিসেবে রাখো, যেটা একটা slice-এর উপর O(1) space-এ (দুটো rolling variable) চলে। মূল function শুধু দুবার সেই helper ডাকে আর `max` নেয়। চাইলে একটা `dp` array, কিন্তু rolling দুই variable-ই যথেষ্ট।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
State আসলে #6-এর মতোই — "কত নম্বর বাড়ি পর্যন্ত best লুট" — শুধু দুটো আলাদা window-তে। তাই flat slice-এর উপর rolling DP নিখুঁত। বৃত্তের জটিলতাটা data structure-এ ঢোকে না; সেটা একটা উঁচু স্তরের case split-এ সামলানো হয়, তাই ভেতরের যন্ত্র সরল থাকে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: সব valid subset দেখো (কোনো দুটো adjacent নয়, এবং 0 ও n-1 একসাথে নয়), max sum নাও।
```text
সব subset S of houses:
if কোনো দুটো S-member পাশাপাশি নয় (বৃত্ত-অর্থে):
track sum(S)
answer = max sum
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
সব subset enumerate করা **O(2^n)** — exponential, আর প্রতিটায় adjacency check। বৃত্ত-constraint যোগ করায় শুধু আরও জটিল হয়, দ্রুত হয় না। অথচ আমরা জানি linear robber O(n)-এ হয় (#6), তাই বৃত্তটাকেও দুটো linear-এ ভেঙে O(n)-এ সারা যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: শুধু একটা জোড়াই (0, n-1) লাইনের চেয়ে বেশি constraint যোগ করে। আর "0 আর n-1 একসাথে নয়" সমান "অন্তত একটা বাদ"। তাই দুটো case — "n-1 বাদ" আর "0 বাদ" — মিলে সব valid সমাধান ধরে, প্রতিটাই একটা সাধারণ linear robber।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** helper `rob_line(a)`-এর ভেতর — `dp[i]` = slice `a`-র বাড়ি `0..i` থেকে সম্ভব max লুট (ঠিক #6)। বাইরের answer = দুই slice-এর rob_line-এর max।
**Transition (helper-এর ভেতর):**
```text
dp[i] = max(dp[i-1], # skip house i
dp[i-2] + a[i]) # rob it -> i-1 নিষিদ্ধ
```
**Case split (বাইরে):**
```text
if n == 1: return nums[0]
answer = max( rob_line(nums[0 : n-1]), # শেষ বাড়ি বাদ
rob_line(nums[1 : n]) ) # প্রথম বাড়ি বাদ
```
**Base case:** helper-এ `dp[0]=a[0]`, `dp[1]=max(a[0],a[1])`; বাইরে single-house আলাদা।
**Answer location:** দুই helper-call-এর `max`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** বৃত্তের wrap-around constraint-কে সরাসরি DP state-এ ঢোকানোর চেষ্টা কোরো না — সেটা messy। বদলে একটা উঁচু-স্তরের সিদ্ধান্তে ("0 ছোঁব কি ছোঁব না") problem-টাকে দুটো পরিচিত linear সমস্যায় কেটে ফেলো। কঠিন constraint-কে কয়েকটা সরল case-এ ভাগ করা — এটা অনেক "circular / wrap-around" problem-এর সাধারণ অস্ত্র।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [2, 7, 9, 3, 1]` (বৃত্তে)। দুটো linear সমস্যায় ভাঙো:
```text
circle: 2 - 7 - 9 - 3 - 1 - (back to 2)
^ ^
house 0 house 4 (adjacent)
case A (drop last): rob_line([2, 7, 9, 3]) # বাড়ি 0 ছুঁতে পারি
case B (drop first): rob_line([7, 9, 3, 1]) # বাড়ি 4 ছুঁতে পারি
answer = max(case A, case B)
rob_line(a): dp[i] = max(dp[i-1], dp[i-2] + a[i]) # ঠিক #6
```
case A → 2 + 9 = 11; case B → 7 + 3 = 10 (বা 9 + 1 = 10); max = 11।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`nums = [1, 2, 3]`:
1. `n = 3`, single-house নয়
2. case A `rob_line([1, 2])`: `dp[0]=1`, `dp[1]=max(1,2)=2` → 2
3. case B `rob_line([2, 3])`: `dp[0]=2`, `dp[1]=max(2,3)=3` → 3
4. answer = `max(2, 3) = 3`
হাতে মিলিয়ে: 0 আর 2 adjacent (বৃত্ত), তাই একসাথে 1+3 নেওয়া যায় না; সেরা single হলো বাড়ি 2 (3)। ✔
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
# ---- helper: linear House Robber (#6), O(1) space ----
def rob_line(a):
take, skip = 0, 0 # take = best ending using last; skip = best skipping last
for x in a:
take, skip = skip + x, max(take, skip)
return max(take, skip)
# ---- way 1: case split (drop first OR drop last) ----
def rob_circle(nums):
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
return max(rob_line(nums[: n - 1]), # শেষ বাড়ি বাদ
rob_line(nums[1:])) # প্রথম বাড়ি বাদ
# ---- way 2: explicit dp-array helper (same logic, array form) ----
def rob_line_arr(a):
if not a:
return 0
if len(a) == 1:
return a[0]
dp = [0] * len(a)
dp[0] = a[0]
dp[1] = max(a[0], a[1])
for i in range(2, len(a)):
dp[i] = max(dp[i - 1], dp[i - 2] + a[i])
return dp[-1]
def rob_circle_arr(nums):
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
return max(rob_line_arr(nums[: n - 1]),
rob_line_arr(nums[1:]))
# ---- tests ----
cases = [
([2, 3, 2], 3),
([1, 2, 3, 1], 4),
([2, 7, 9, 3, 1], 11),
([5], 5),
([2, 3], 3),
([1, 2, 3], 3),
([200, 3, 140, 20, 10], 340), # 200 + 140
([0, 0, 0], 0),
]
for nums, want in cases:
assert rob_circle(nums) == want, (nums, rob_circle(nums))
assert rob_circle_arr(nums) == want, (nums, rob_circle_arr(nums))
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `rob_line`: #6-এর O(1) robber; `take` = এই element নিয়ে best, `skip` = এটা বাদ দিয়ে best; এক assignment-এ এগোয়, শেষে `max`।
- `rob_circle`: খালি ও single-house আলাদা; নয়তো দুই slice (`[:n-1]` শেষ বাদ, `[1:]` প্রথম বাদ)-এর `rob_line`-এর max।
- `rob_line_arr` / `rob_circle_arr`: একই algorithm, কিন্তু helper-এ explicit `dp` array — দেখায় rolling আর array দুই form-ই একই উত্তর দেয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ আটটা input: `[2,3,2]` (3, কারণ প্রান্ত-দুটো adjacent), `[1,2,3,1]` (4), classic `[2,7,9,3,1]` (11), single (5), দুই-বাড়ি (3), `[1,2,3]` (3), একটা bigger `[200,3,140,20,10]` (200+140 = 340), আর সব-শূন্য (0)। প্রতিটার জন্য দুই function-ই (rolling + array) একই উত্তর দিতে হবে। সব pass হলে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
- দুই version-ই **O(n)** — helper দুবার চলে, প্রতিবার O(n)। (Naive subset enumeration ছিল O(2^n)।)
### অতিরিক্ত জায়গা {#19-space-complexity}
- `rob_circle` (rolling helper): **O(n)** শুধু slice তৈরির জন্য, helper নিজে **O(1)**; চাইলে index-range পাঠিয়ে slice-ও এড়ানো যায়।
- `rob_circle_arr`: **O(n)** — `dp` array।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- single-house edge না সামলানো — `n == 1`-এ slice `nums[:0]` খালি হয়ে answer ভুল 0 দেয়; আলাদা return লাগে।
- দুটো case-এর বদলে শুধু একটা চালানো (যেমন শুধু "শেষ বাদ") — তখন এমন সমাধান হারাবে যেখানে শেষ বাড়িই সেরা।
- প্রথম আর শেষ "একসাথে নয়" নিয়মটা ভুলে গিয়ে সাধারণ linear robber চালানো — তখন `[2,3,2]`-এ ভুল করে 4 (2+2) আসবে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: #6 House Robber-এর take-or-skip core, একটা case split দিয়ে মুড়ে। #6-এর note আর [../state-transition-thinking.md](../state-transition-thinking.md)-এর "Problem 2 — House Robber"-এই linear DP-টা আছে; এখানে শুধু বৃত্ত-constraint-এর জন্য দুবার চালানো।
### পরের অনুশীলন {#22-similar-harder-problems}
- House Robber III (বাড়িগুলো গাছে, tree DP) —