Grid Unique Paths II
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
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.dynamic_programming;
import java.util.*;
/ * Problem: Grid Unique Paths II * Group: 11. Dynamic Programming */ / * ============================================================================================ * PROBLEM: Grid Unique Paths II * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Find unique paths from (0,0) to (N-1, M-1) in a grid with obstacles. * - 0 = Empty, 1 = Obstacle. * - Move Down or Right. * - Return answer % (10^9 + 7). * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Identical logic to "Unique Paths in a Grid", but with Modulo Arithmetic. * * Let MOD = 1000000007. * * Recurrence: * If A[i][j] == 1: dp[i][j] = 0 * Else: dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD * * Base Case Initialization: * - If A[0][0] == 1, return 0 immediately. * - dp[0][0] = 1. * - Initialize first row and column carefully (if cell is obstacle or prev is 0, current is 0). * * --------------------- * 3. Constraints & Complexity * --------------------- * Constraints: * 1 <= N, M <= 500 * * Time Complexity: O(N * M) * Space Complexity: O(N * M) or O(M) * * ============================================================================================ */ public class GridUniquePathsII { public int solve(int[][] A) { // TODO: Implement solution return 0; } }