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!