Unique Paths in a Grid

Logical Breakdown

• [ ] Subproblem Identification:
• [ ] Optimal Substructure:
• [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
• [ ] Optimization: (Matrix Exponentiation if 'A' is huge)

---

Mathematical Rigor

State Definition

Let \(dp[i]\) be the state for the \(i\)-th subproblem.

Recurrence Relation

\[ dp[i] = ... \]

---

Visualization

graph TD A["Current State"] --> B["Previous State 1"] A --> C["Previous State 2"]

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Iterative DP	\(O(N)\)	\(O(1)\)

---

Code Reference

package com.dsa.dynamic_programming;

import java.util.*;

/ * Problem: Unique Paths in a Grid * Group: 11. Dynamic Programming */ / * ============================================================================================ * PROBLEM: Unique Paths in a Grid * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given a grid of size n * m. * - Start at (1, 1). Goal is (n, m). * - Movement: (x, y) -> (x, y + 1) [Right] OR (x + 1, y) [Down]. * - Obstacles are marked as 1, empty space as 0. * - Return total unique paths. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * This is a classic 2D Dynamic Programming problem. * Let dp[i][j] be the number of unique paths to reach cell (i, j). * * Recurrence Relation: * To reach (i, j), we must come from either the Top (i-1, j) or the Left (i, j-1). * * 1. If grid[i][j] == 1 (Obstacle): * dp[i][j] = 0 (Path blocked). * * 2. If grid[i][j] == 0 (Empty): * dp[i][j] = dp[i-1][j] + dp[i][j-1] * * Base Case: * - Start Point (0,0): If grid[0][0] == 0, then dp[0][0] = 1. Else 0. * - First Row: dp[0][j] = dp[0][j-1] (If obstacle, it becomes 0 for all subsequent cols). * - First Col: dp[i][0] = dp[i-1][0] (If obstacle, it becomes 0 for all subsequent rows). * * Note on Indexing: * The problem mentions 1-based indexing for description, but input is usually 0-based. * We will assume 0-based indexing for implementation logic. * * --------------------- * 3. Constraints & Complexity * --------------------- * Time Complexity: O(N * M) - Iterate through the grid once. * Space Complexity: O(N * M) or O(M) if using space optimization (only previous row needed). * * ============================================================================================ */ public class UniquePathsInAGrid { public int solve(int A) { // TODO: Implement solution return 0; }

public int uniquePathsWithObstacles(int[][] grid3) {
    return 1;
}

}