007 — Unique Paths¶

Source¶

Original source: Classic grid counting DP exercise
Platform: LeetCode — https://leetcode.com/problems/unique-paths/
Topic: dynamic programming
Difficulty: Medium
Pattern: Grid DP (counting)
Basic idea inherited from: #2 Climbing Stairs — কিন্তু এক লাইনের বদলে 2D grid-এ

1. Problem in simple words¶

একটা m × n grid আছে। তুমি বাঁ-উপরের কোণ (top-left) থেকে শুরু করে ডান-নিচের কোণে (bottom-right) যেতে চাও। প্রতি ধাপে শুধু ডানে (right) বা নিচে (down) যেতে পারো। কতগুলো আলাদা path আছে, সেটা গোনো।

3 x 3 grid:
    S . .
    . . .
    . . E
S থেকে E-তে যাওয়ার মোট 6 টা আলাদা path

2. Which basic idea does this inherit from?¶

ভিত্তি #2 Climbing Stairs-এর counting চিন্তা — "শেষ move কোথা থেকে এলো?" দিয়ে ভাঙা। সেখানে এক লাইনে শেষ move ছিল 1 বা 2 ধাপ; এখানে 2D grid-এ একটা cell-এ ঢোকার শেষ move হয় উপর থেকে, নয় বাঁ থেকে — দুটো option, ঠিক দুটো ছোট cell-এর ways যোগ।

3. What is the hidden math or logic?¶

লুকানো logic: cell (r, c)-তে ঢোকার শেষ move-টা এসেছে হয় ঠিক উপরের cell (r-1, c) থেকে (একটা down), নয় ঠিক বাঁয়ের cell (r, c-1) থেকে (একটা right)। এই দুটো দল disjoint আর সব path cover করে। তাই (r, c)-তে পৌঁছানোর path-সংখ্যা = উপরের cell-এর path + বাঁয়ের cell-এর path।

4. Which data structure is needed?¶

একটা 2D array dp (size m × n), যেখানে dp[r][c] = start থেকে cell (r, c) পর্যন্ত path-এর সংখ্যা। চাইলে শুধু এক row রেখে O(n) space-এ করা যায়, কারণ প্রতিটা cell শুধু উপরের আর বাঁয়ের cell পড়ে।

5. Why this data structure fits¶

State এখানে দুটো সংখ্যা: row r আর column c — তাই 2D array নিখুঁত। dp[r][c] cell (r,c)-এর উত্তর ধরে। যেহেতু dependency শুধু উপরে আর বাঁয়ে, row-by-row বাঁ-থেকে-ডান ভরলে দুটো dependency-ই আগে তৈরি; আর শুধু আগের row লাগে বলে এক row-তে compress করা যায়।

6. Real-life analogy¶

ভাবো একটা শহরের block-grid, তুমি বাঁ-উপরের চৌরাস্তা থেকে ডান-নিচের চৌরাস্তায় যাচ্ছ, শুধু পূর্ব (ডান) আর দক্ষিণে (নিচ) হাঁটো। যেকোনো চৌরাস্তায় পৌঁছানোর মোট পথ = ঠিক পশ্চিমের চৌরাস্তা থেকে আসা পথ + ঠিক উত্তরের চৌরাস্তা থেকে আসা পথ — কারণ শেষ block-টা ওই দুদিকের একটা থেকেই হাঁটা।

7. Visual explanation¶

dp[r][c] = start থেকে (r,c) পর্যন্ত path। 3 × 3 grid:

প্রথম row আর প্রথম column সব 1 (একটাই দিক দিয়ে যাওয়া যায়):

    c=0  c=1  c=2
r=0  1    1    1
r=1  1    ?    ?
r=2  1    ?    ?

dp[r][c] = dp[r-1][c] + dp[r][c-1]

dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3
dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6   <- answer

    c=0  c=1  c=2
r=0  1    1    1
r=1  1    2    3
r=2  1    3    6

প্রতিটা cell = উপরের cell + বাঁয়ের cell। (এটা আসলে Pascal's triangle, ঘুরিয়ে।)

8. Example input and output¶

Input : m = 3, n = 3   -> Output: 6
Input : m = 3, n = 7   -> Output: 28
Input : m = 3, n = 2   -> Output: 3

Edge case 1: m = 1, n = 1   -> Output: 1   (শুরু = শেষ, একটাই "path")
Edge case 2: m = 1, n = 5   -> Output: 1   (শুধু ডানে, একটাই path)

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা cell থেকে recurse করে দুই দিকের path যোগ করা — ডানে যাও আর নিচে যাও।

paths(r, c):                     # (r,c) থেকে নিচ-ডান কোণে পথ
    if r == m-1 and c == n-1: return 1   # পৌঁছে গেছি
    if r >= m or c >= n: return 0         # grid-এর বাইরে
    return paths(r+1, c) + paths(r, c+1)
answer = paths(0, 0)

10. Why brute force is slow¶

এই recursion exponential (মোটামুটি O(2^(m+n))) — প্রতিটা cell দুটো শাখা খোলে, আর একই cell বহু পথ দিয়ে বারবার গোনা হয় (overlapping subproblems)। মাঝখানের cell-গুলো সবচেয়ে বেশি repeat হয়। grid একটু বড় হলেই এটা অসম্ভব ধীর।

11. Key observation¶

মূল observation: distinct cell মাত্র m × n-টা। প্রতিটা cell-এর path-সংখ্যা একবার গুনে রাখলে, প্রতিটা শুধু দুটো প্রতিবেশী cell যোগ করে পাওয়া যায় — exponential কাজ O(mn)-এ নেমে আসে।

12. Optimized intuition¶

State (শব্দে): dp[r][c] = start cell (0,0) থেকে cell (r, c) পর্যন্ত পৌঁছানোর distinct path-এর সংখ্যা।

Transition:

dp[r][c] = dp[r-1][c] + dp[r][c-1]

কারণ: (r,c)-তে ঢোকার শেষ move উপর থেকে বা বাঁ থেকে — দুটো disjoint দল।

Base case: dp[0][0] = 1। প্রথম row আর প্রথম column-এর প্রতিটা cell-এ পৌঁছানোর একটাই দিক, তাই সব 1 (grid-এর বাইরের প্রতিবেশীকে 0 ধরলে এটা এমনিই বেরিয়ে আসে)।

Answer location: dp[m-1][n-1]।

Memoization (top-down): উপরের paths(r,c) recursion-টাই রাখো, dict যোগ করো। Tabulation (bottom-up): প্রথম row/column 1 দিয়ে শুরু করে row-by-row বাঁ-থেকে-ডান ভরো। শুধু আগের row লাগে বলে এক row rolling করে O(n) space।

13. Thinking tweak¶

মোচড়: "পুরো path গুনব" না ভেবে প্রতিটা cell-এ ছোট প্রশ্ন করো — "এখানে এলাম কোথা থেকে?" উত্তর মাত্র দুটো (উপর বা বাঁ)। তখন Climbing Stairs-এর এক-মাত্রিক counting সরাসরি দুই-মাত্রায় বসে যায়। Grid DP-র এটাই মূল লাফ: 1D counting-কে দুই দিকের যোগে বাড়ানো।

14. Step-by-step dry run¶

m = 3, n = 2, tabulation:

প্রথম column সব 1: dp[0][0]=dp[1][0]=dp[2][0]=1
প্রথম row সব 1: dp[0][0]=dp[0][1]=1
dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
return dp[2][1] = 3

হাতে মিলিয়ে: 3 সারি 2 কলামে — DDR, DRD, RDD = ঠিক 3 টা path। ✔

15. Python solution¶

import math

# ---- way 1: memoization (top-down) ----
def unique_paths_memo(m, n):
    memo = {}
    def paths(r, c):
        if r == 0 or c == 0:                 # প্রথম row/column: একটাই path
            return 1
        if (r, c) in memo:
            return memo[(r, c)]
        memo[(r, c)] = paths(r - 1, c) + paths(r, c - 1)
        return memo[(r, c)]
    return paths(m - 1, n - 1)

# ---- way 2: tabulation (bottom-up), full grid ----
def unique_paths_tab(m, n):
    dp = [[1] * n for _ in range(m)]         # প্রথম row/column 1 দিয়ে initialized
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    return dp[m - 1][n - 1]

# ---- way 3: O(n) space (এক row rolling) ----
def unique_paths_row(m, n):
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]            # row[c]=উপর (পুরোনো), row[c-1]=বাঁ (নতুন)
    return row[n - 1]

# ---- tests ----
cases = [
    (3, 3, 6),
    (3, 7, 28),
    (3, 2, 3),
    (1, 1, 1),
    (1, 5, 1),
    (5, 1, 1),
    (4, 4, 20),
]
for m, n, want in cases:
    assert unique_paths_memo(m, n) == want, (m, n, unique_paths_memo(m, n))
    assert unique_paths_tab(m, n) == want, (m, n, unique_paths_tab(m, n))
    assert unique_paths_row(m, n) == want, (m, n, unique_paths_row(m, n))
    # closed-form check: C(m+n-2, m-1)
    assert want == math.comb(m + n - 2, m - 1)

print("সব test pass!")

16. Line-by-line code explanation¶

unique_paths_memo: paths(r,c) cell (r,c)-এর path-সংখ্যা দেয়; r==0 or c==0 → 1 (একটাই দিক); memo repeated কাজ এড়ায়।
unique_paths_tab: পুরো grid 1 দিয়ে শুরু (প্রথম row/column ঠিক হয়ে যায়); ভেতরের cell-গুলো উপর+বাঁ যোগ; answer dp[m-1][n-1]।
unique_paths_row: এক row রাখি; row[c] += row[c-1]-এ row[c] তখনো পুরোনো (উপরের মান) আর row[c-1] নতুন (বাঁয়ের মান) — তাই এক array-তেই কাজ হয়।

17. Output walkthrough¶

cases-এ সাতটা (m, n) input আর সঠিক উত্তর — দুটো LeetCode example, কয়েকটা edge (single row/column/cell), আর 4×4 = 20। প্রতিটার জন্য তিন function মিলতে হবে, এবং উত্তরটা closed-form combination C(m+n-2, m-1)-এর সাথেও মেলানো হয় (cross-check)। সব pass হলে শেষে print: সব test pass!।

18. Time complexity¶

Memoization ও tabulation: O(m·n) — প্রতিটা cell একবার করে।
Row version: O(m·n) time, কিন্তু কম space।

(Naive recursion ছিল প্রায় O(2^(m+n))।)

19. Space complexity¶

Memoization: O(m·n) — dict + recursion stack।
Full tabulation: O(m·n) — 2D array।
Row version: O(n) — এক row।

20. Common mistakes¶

প্রথম row/column 1 দিয়ে initialize না করা — তখন ভেতরের cell-গুলো ভুল (0 থেকে শুরু) হয়ে যায়।
row-rolling version-এ row[c] = row[c] + row[c-1]-এর order ভুল বোঝা — row[c-1] অবশ্যই এই pass-এ আগে update হওয়া (বাঁ), row[c] আগের pass-এর (উপর); বাঁ-থেকে-ডান গেলে এটা এমনিই ঠিক।
m আর n গুলিয়ে ফেলা — counting-এ উত্তর symmetric (C(m+n-2, m-1)), তাই ভুল ধরা পড়ে না, কিন্তু obstacle version (#8)-এ ধরা পড়বে।

21. Which basic problem this inherits from¶

ভিত্তি: #2 Climbing Stairs-এর counting, 2D-তে তোলা। ../state-transition-thinking.md-এর "Problem 4 — Grid Paths" section-এ ঠিক এই 5-step আর fill-order-এর geometry আলোচনা আছে; ../patterns.md-এর "Grid DP" family-ও এখানে।

22. Similar harder problems¶

Grid Paths with obstacles (কিছু cell blocked) — https://cses.fi/problemset/task/1638 (এই tracker-এর #8)
Minimum Path Sum (counting-এর বদলে min cost) — https://leetcode.com/problems/minimum-path-sum/ (#9)
Unique Paths II (obstacle version, LeetCode) — https://leetcode.com/problems/unique-paths-ii/

23. Pattern learned¶

Grid DP (counting): state দুটো index (r, c), transition উপরের আর বাঁয়ের cell-এর যোগ, fill order row-by-row বাঁ-থেকে-ডান (transition arrow-এর geometry থেকেই বেরোয়)। শুধু আগের row লাগে বলে O(n) space-এ নামে। অনেক grid problem-এর কঙ্কাল এটাই।

24. Final summary¶

ভবিষ্যতের আমাকে: "Unique Paths = 2D Climbing Stairs।" State dp[r][c] = (r,c)-তে পৌঁছানোর ways, transition dp[r][c] = dp[r-1][c] + dp[r][c-1], base প্রথম row/column = 1। মনে রেখো: fill order arrow-এর দিক থেকেই বেরোয় (উপর+বাঁ → row-by-row), আর এক row-তে compress করা যায়।

25. JavaScript solution (with test cases)¶

Grid DP (counting); dp[r][c] = dp[r-1][c] + dp[r][c-1]। 2D array বানাতে Array.from — .fill([]) নয়।

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// full 2D grid: প্রথম row/column 1, ভেতরে উপর+বাঁ
function uniquePathsTab(m, n) {
  // প্রতিটা row আলাদা array (shared-ref bug এড়িয়ে)
  const dp = Array.from({ length: m }, () => new Array(n).fill(1));
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
    }
  }
  return dp[m - 1][n - 1];
}
// O(n) space: এক row rolling
function uniquePathsRow(m, n) {
  const row = new Array(n).fill(1);
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) row[c] += row[c - 1];   // row[c]=উপর, row[c-1]=বাঁ
  }
  return row[n - 1];
}
// closed-form cross-check: C(m+n-2, m-1)
function comb(a, b) { let res = 1; for (let i = 0; i < b; i++) res = res * (a - i) / (i + 1); return Math.round(res); }
// ---- test cases (example + edge) ----
const cases = [[3, 3, 6], [3, 7, 28], [3, 2, 3], [1, 1, 1], [1, 5, 1], [5, 1, 1], [4, 4, 20]];
for (const [m, n, want] of cases) {
  assert(uniquePathsTab(m, n) === want, "tab " + m + "x" + n);
  assert(uniquePathsRow(m, n) === want, "row " + m + "x" + n);
  assert(comb(m + n - 2, m - 1) === want, "comb " + m + "x" + n);
}
console.log("সব JS test pass!");

JS টীকা: 2D DP grid বানাতে Array.from({length: m}, () => new Array(n).fill(1)) — প্রতিটা () => ... call নতুন row দেয়। new Array(m).fill(new Array(n)) দিলে সব row একই array reference পেত, এক cell বদলালে সব row-তে দেখা যেত (নীরব ভয়ংকর bug)। inner new Array(n).fill(1)-এ 1 primitive, তাই সেটা নিরাপদ।

26. TypeScript solution (with test cases)¶

function uniquePaths(m: number, n: number): number {
  const dp: number[][] = Array.from({ length: m }, () => new Array<number>(n).fill(1));
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
    }
  }
  return dp[m - 1][n - 1];
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
const cases: Array<[number, number, number]> = [
  [3, 3, 6], [3, 7, 28], [3, 2, 3], [1, 1, 1], [1, 5, 1], [4, 4, 20],
];
for (const [m, n, want] of cases) expect(uniquePaths(m, n), want, `${m}x${n}`);
console.log("সব TS test pass!");

TS টীকা: dp: number[][] declare করায় grid যে number-এর 2D array তা locked; new Array<number>(n) generic দিয়ে element-type স্পষ্ট, ভুল type push আটকায়। cases: Array<[number, number, number]> tuple-type প্রতিটা case-এর গঠন (m, n, expected) নিশ্চিত করে।

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

Robot / agent path counting: grid-এ এক কোণ থেকে আরেক কোণে নির্দিষ্ট দিকের (right/down) কত পথ — robotics ও game level analysis।
Combinatorial counting: আসলে এটা C(m+n-2, m-1) — lattice path গোনা, যা probability ও combinatorics-এ বহুল।
Grid-based game design: কত উপায়ে এক টোকেন board পার করতে পারে তা মেপে difficulty balance করা।
Routing on a mesh: packet বা delivery route-এ monotone (একদিকে অগ্রসর) পথের সংখ্যা।
DP foundation: এই counting-grid-ই Minimum Path Sum, obstacle-grid ইত্যাদির ভিত — operator (+→min) বদলেই বহু variant।

মূল pattern: state দুটো index (r,c), transition উপর+বাঁ cell-এর যোগ; শুধু আগের row লাগে বলে O(n) space-এ নামে।

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