9.8 Grid Paths

চিনবেন কীভাবে

from top-left to bottom-right of a grid, "how many paths" or "min cost path" — dp[i][j] = from above + from the left

Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

Demo: Unique Paths — LC 62 (Medium — Google/Meta High)

Statement (Demo): A robot at the top-left of an m × n grid moves only down or right. Return the number of unique paths to the bottom-right. Example: m=3, n=7 → 28 | ⚡ m,n ≤ 100

Approach: Each cell is reached from above or from the left — dp[i][j] = dp[i-1][j] + dp[i][j-1]. One row is enough: roll it in place.

function uniquePaths(m, n) {
  const dp = new Array(n).fill(1); // the first row
  for (let i = 1; i < m; i++) for (let j = 1; j < n; j++) dp[j] += dp[j - 1]; // above (old dp[j]) + left
  return dp[n - 1];
}

Complexity: Time O(m·n), Space O(n)

প্রবলেম

Minimum Path Sumplan · দিন ০৪৭ LC 64
Statement: Given an m × n grid of non-negative numbers, moving only down or right, return the minimum sum of a path from top-left to bottom-right.
Example: grid=[[1,3,1],[1,5,1],[4,2,1]] → 7 (1→3→1→1→1) | ⚡ m,n ≤ 200
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Knight Probability in ChessboardLC 688
(probability DP — state (move, cell), probabilities add up)
Statement: A knight starts at (r, c) on an n × n board and makes k uniformly random moves. Return the probability that it is still on the board afterwards.
Example: n=3, k=2, r=0, c=0 → 0.0625 | ⚡ n ≤ 25, k ≤ 100
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে