Answer: Databricks OA Question 2024 September | Dynamic Programming | on-campus

Solution: Unique Paths — Space Optimized 1D DP Approach We use Dynamic Programming. The number of ways to reach any cell (i, j) equals the sum of paths from the cell above (i-1, j) and the cell to the left (i, j-1): dp[i][j] = dp[i-1][j] + dp[i][j-1] Base case: All cells in the first row and first column have exactly 1 path (the robot can only move in one direction to reach them). We optimize from a 2D DP table ...