Welcome back to our voyage through algorithmic mazes! In this section, we'll bring Dynamic Programming (DP) to life by examining how it elegantly solves classic maze-related problems. Remember, the core idea of DP is to break down a complex problem into smaller, overlapping subproblems, solve each subproblem only once, and store their solutions to avoid redundant computations. Think of it as leaving breadcrumbs in the maze so you don't get lost retracing your steps.
Let's start with a fundamental maze-solving problem: finding the number of unique paths from the top-left corner to the bottom-right corner of a grid. Imagine a grid where you can only move right or down. This problem, though simple, beautifully illustrates the DP principle of building up solutions from smaller ones.
graph TD
A[Start] --> B{Can move Right/Down}
B --> C[Reach Destination]
C --> D[Count Paths]
Consider a grid of size M x N. Let dp[i][j] represent the number of unique paths to reach cell (i, j). To reach (i, j), you could have come from (i-1, j) (moving down) or from (i, j-1) (moving right). Therefore, the number of paths to (i, j) is the sum of paths to (i-1, j) and (i, j-1). This gives us our recurrence relation: dp[i][j] = dp[i-1][j] + dp[i][j-1].
What about the base cases? The cells in the first row (i=0) and the first column (j=0) can only be reached in one way: by moving only right or only down, respectively, from the start. So, dp[0][j] = 1 for all j, and dp[i][0] = 1 for all i.
function uniquePaths(m, n) {
const dp = Array(m).fill(0).map(() => Array(n).fill(0));
// Base cases: Fill the first row and first column with 1s
for (let i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (let j = 0; j < n; j++) {
dp[0][j] = 1;
}
// Fill the rest of the dp table using the recurrence relation
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
// The result is the value in the bottom-right cell
return dp[m - 1][n - 1];
}This approach effectively builds a table where each cell's value is computed based on previously computed values, avoiding recalculations. The time complexity here is O(MN) because we visit each cell in the grid once, and the space complexity is also O(MN) for storing the DP table. We've indeed remembered our past steps!
Now, let's consider a slightly more complex variation: a maze with obstacles. Imagine a grid where some cells are blocked. We want to find the number of unique paths from the top-left to the bottom-right, but we cannot step on an obstacle.
If a cell (i, j) contains an obstacle, then no paths can go through it. This means dp[i][j] should be 0 for any cell with an obstacle. Our recurrence relation needs a slight modification to account for this. If grid[i][j] is an obstacle, dp[i][j] = 0. Otherwise, dp[i][j] = dp[i-1][j] + dp[i][j-1].
function uniquePathsWithObstacles(obstacleGrid) {
const m = obstacleGrid.length;
const n = obstacleGrid[0].length;
// If the starting cell has an obstacle, there are no paths
if (obstacleGrid[0][0] === 1) {
return 0;
}
const dp = Array(m).fill(0).map(() => Array(n).fill(0));
// Base case: Starting cell
dp[0][0] = 1;
// Fill the first column
for (let i = 1; i < m; i++) {
if (obstacleGrid[i][0] === 0 && dp[i - 1][0] === 1) {
dp[i][0] = 1;
} else {
dp[i][0] = 0; // If obstacle or previous cell unreachable
}
}
// Fill the first row
for (let j = 1; j < n; j++) {
if (obstacleGrid[0][j] === 0 && dp[0][j - 1] === 1) {
dp[0][j] = 1;
} else {
dp[0][j] = 0; // If obstacle or previous cell unreachable
}
}
// Fill the rest of the dp table
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (obstacleGrid[i][j] === 1) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}In this version, the presence of an obstacle acts as a wall, stopping paths. Our DP table now accurately reflects these impassable barriers. The principles remain the same: break it down, solve subproblems, and store results. These examples demonstrate the power and versatility of Dynamic Programming in navigating through complex computational landscapes, much like finding your way through a challenging maze.