773. Sliding Puzzle
Problem Description
You have a 2x3 game board with tiles numbered 1 through 5 and one empty space (represented as 0). The tiles can slide into the empty space if they are directly adjacent to it (up, down, left, or right - no diagonal moves).
The goal is to rearrange the tiles to reach the target configuration:
[[1, 2, 3], [4, 5, 0]]
In this target state, the numbers 1-5 are arranged in order from left to right, top to bottom, with the empty space (0) in the bottom-right corner.
A move consists of sliding one tile that is adjacent to the empty space into that empty position (equivalently, swapping the 0 with an adjacent number).
Given an initial board configuration, you need to find the minimum number of moves required to reach the target state. If it's impossible to reach the target state from the given configuration, return -1
.
For example, if the initial board is:
[[1, 2, 3], [4, 0, 5]]
You can slide the 5 into the empty space (where 0 is) to get the target configuration in just 1 move.
The solution uses BFS (Breadth-First Search) to explore all possible board states level by level, ensuring the shortest path is found. The board states are converted to strings for efficient storage and comparison in the visited set.
Flowchart Walkthrough
First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: The sliding puzzle can be represented as a graph where each board state is a node, and edges connect states that can be reached through a single tile move.
Is it a tree?
- No: The state space is not a tree because multiple paths can lead to the same board configuration (you can often reach the same state through different sequences of moves).
Is the problem related to directed acyclic graphs?
- No: The state graph can have cycles (you can return to a previous state by reversing moves).
Is the problem related to shortest paths?
- Yes: We need to find the minimum number of moves to reach the target state, which is essentially finding the shortest path from the initial state to the goal state.
Is the graph Weighted?
- No: Each move has the same cost (1 move), so this is an unweighted graph where all edges have equal weight.
BFS
- Yes: For unweighted shortest path problems, BFS is the optimal choice.
Conclusion: The flowchart suggests using BFS (Breadth-First Search) for finding the minimum number of moves in the sliding puzzle. BFS explores states level by level, guaranteeing that when we first reach the target state, we've found it via the shortest possible path (minimum number of moves).
Intuition
The key insight is to think of this puzzle as a graph traversal problem. Each possible board configuration is a node in our graph, and moving a tile creates an edge between two configurations. Since we want the minimum number of moves, we're looking for the shortest path from our starting configuration to the target configuration [[1,2,3],[4,5,0]]
.
Why BFS? When all moves have equal cost (each move counts as 1), BFS naturally finds the shortest path because it explores all configurations reachable in 1 move, then all configurations reachable in 2 moves, and so on. The first time we encounter our target, we've found it using the minimum number of moves.
To implement this, we need to:
- Represent board states efficiently: Converting the 2D board to a string like
"123450"
makes it easy to store in a set and check for duplicates - Track visited states: We use a set to avoid revisiting the same configuration, preventing infinite loops
- Generate all possible next states: From any configuration, we find where the empty space (0) is, then try swapping it with each adjacent tile (up, down, left, right)
- Level-by-level exploration: Using a queue, we process all states at distance
k
before moving to states at distancek+1
The solution converts between board representation and string representation (gets()
and setb()
) for efficient state management. The function f()
generates all valid next states by finding the empty space and swapping it with adjacent tiles. If we exhaust all possible states without finding the target, the puzzle is unsolvable, so we return -1
.
Learn more about Breadth-First Search, Memoization, Dynamic Programming and Backtracking patterns.
Solution Approach
The implementation uses BFS with string representation of board states. Let's walk through the key components:
1. State Representation
- Convert the 2D board to a string for efficient storage and comparison
gets()
: Flattens the 2D board into a string by concatenating rows (e.g.,[[1,2,3],[4,0,5]]
becomes"123405"
)setb(s)
: Reconstructs the 2D board from a string representation
2. Generating Next States (f()
function)
- Find the position
(i, j)
of the empty space (0) in the current board - Try moving the empty space in 4 directions:
[[0, -1], [0, 1], [1, 0], [-1, 0]]
(left, right, down, up) - For each valid adjacent position
(x, y)
:- Swap the empty space with the adjacent tile
- Convert to string and add to results
- Swap back to restore original state (backtrack)
3. BFS Implementation
start = gets() # Initial board state as string end = "123450" # Target state vis = {start} # Visited states set q = deque([start]) # BFS queue ans = 0 # Move counter
4. Level-by-Level Traversal
- Process all states at current distance before incrementing
ans
- For each state in the current level:
- Convert string back to board using
setb(x)
- Generate all possible next states using
f()
- If target state found, return current move count
- Add unvisited states to queue and visited set
- Convert string back to board using
5. Early Termination
- Check if initial state equals target (return 0)
- Return
-1
if queue empties without finding target (unsolvable)
The algorithm guarantees finding the minimum moves because BFS explores states in order of distance from the start. Time complexity is O(n!)
where n
is the number of tiles (6 in this case), as there are at most 6!
possible board configurations. Space complexity is also O(n!)
for storing visited states.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a simple example where the initial board is:
[[1, 2, 3], [4, 0, 5]]
And we want to reach the target:
[[1, 2, 3], [4, 5, 0]]
Step 1: Initialize BFS
- Convert initial board to string:
"123405"
- Target string:
"123450"
- Initialize queue with
["123405"]
and visited set with{"123405"}
- Set move counter
ans = 0
Step 2: Process Level 0 (Initial State)
- Queue size = 1, so we process 1 state at this level
- Pop
"123405"
from queue - Convert back to board:
[[1,2,3],[4,0,5]]
- Find empty space (0) at position (1, 1)
Step 3: Generate Next States From position (1, 1), the empty space can move:
- Up (1-1, 1) = (0, 1): Swap with 2
- New board:
[[1,0,3],[4,2,5]]
→ String:"103425"
- New board:
- Down (1+1, 1) = (2, 1): Invalid (out of bounds)
- Left (1, 1-1) = (1, 0): Swap with 4
- New board:
[[1,2,3],[0,4,5]]
→ String:"123045"
- New board:
- Right (1, 1+1) = (1, 2): Swap with 5
- New board:
[[1,2,3],[4,5,0]]
→ String:"123450"
✓ Target found!
- New board:
Step 4: Check for Target
- When generating the right move, we get
"123450"
which equals our target - Since we're still processing level 0, we increment
ans
to 1 - Return
ans = 1
The minimum number of moves is 1 (sliding the 5 left into the empty space).
Alternative Example - Multiple Moves: If the initial board was:
[[4, 1, 2], [5, 0, 3]]
String: "412503"
The BFS would explore:
- Level 0: Initial state
"412503"
- Level 1: States reachable in 1 move from initial
- Move 0 up:
"402513"
- Move 0 left:
"412053"
- Move 0 right:
"412530"
- Move 0 up:
- Level 2: States reachable in 2 moves (from unvisited Level 1 states)
- Continue until target
"123450"
is found or all states exhausted
Each level represents states reachable with exactly that many moves, ensuring we find the minimum path when we first encounter the target.
Solution Implementation
1class Solution:
2 def slidingPuzzle(self, board: List[List[int]]) -> int:
3 """
4 Solve the sliding puzzle problem using BFS.
5 Goal: Transform the board to [[1,2,3],[4,5,0]]
6 Returns minimum number of moves, or -1 if impossible.
7 """
8
9 def board_to_string() -> str:
10 """Convert 2D board to string representation for hashing."""
11 result = []
12 for row in range(2):
13 for col in range(3):
14 result.append(str(board[row][col]))
15 return ''.join(result)
16
17 def string_to_board(state: str) -> None:
18 """Convert string representation back to 2D board."""
19 for row in range(2):
20 for col in range(3):
21 board[row][col] = int(state[row * 3 + col])
22
23 def get_next_states() -> List[str]:
24 """Generate all possible next states from current board configuration."""
25 next_states = []
26
27 # Find the position of the empty tile (0)
28 zero_row, zero_col = next((i, j) for i in range(2) for j in range(3) if board[i][j] == 0)
29
30 # Try moving the empty tile in all four directions
31 directions = [[0, -1], [0, 1], [1, 0], [-1, 0]] # left, right, down, up
32
33 for delta_row, delta_col in directions:
34 new_row = zero_row + delta_row
35 new_col = zero_col + delta_col
36
37 # Check if the new position is within bounds
38 if 0 <= new_row < 2 and 0 <= new_col < 3:
39 # Swap empty tile with adjacent tile
40 board[zero_row][zero_col], board[new_row][new_col] = board[new_row][new_col], board[zero_row][zero_col]
41 next_states.append(board_to_string())
42 # Swap back to restore original state
43 board[zero_row][zero_col], board[new_row][new_col] = board[new_row][new_col], board[zero_row][zero_col]
44
45 return next_states
46
47 # Initialize BFS
48 start_state = board_to_string()
49 target_state = "123450"
50
51 # Check if already solved
52 if start_state == target_state:
53 return 0
54
55 # BFS setup
56 visited = {start_state}
57 queue = deque([start_state])
58 moves = 0
59
60 # BFS traversal
61 while queue:
62 moves += 1
63 # Process all states at current level
64 for _ in range(len(queue)):
65 current_state = queue.popleft()
66 string_to_board(current_state)
67
68 # Explore all possible next states
69 for next_state in get_next_states():
70 if next_state == target_state:
71 return moves
72
73 if next_state not in visited:
74 visited.add(next_state)
75 queue.append(next_state)
76
77 # No solution found
78 return -1
79
1class Solution {
2 // Array to store string representation of the board (6 cells total for 2x3 board)
3 private String[] boardStringArray = new String[6];
4 // 2D array representing the current board state
5 private int[][] board;
6
7 /**
8 * Solves the sliding puzzle problem using BFS
9 * @param board Initial 2x3 board configuration
10 * @return Minimum number of moves to reach target state, or -1 if impossible
11 */
12 public int slidingPuzzle(int[][] board) {
13 this.board = board;
14
15 // Convert initial board to string representation
16 String startState = gets();
17 String targetState = "123450";
18
19 // Check if already in target state
20 if (targetState.equals(startState)) {
21 return 0;
22 }
23
24 // BFS setup: visited set and queue
25 Set<String> visited = new HashSet<>();
26 Deque<String> queue = new ArrayDeque<>();
27 queue.offer(startState);
28 visited.add(startState);
29
30 int moves = 0;
31
32 // BFS traversal
33 while (!queue.isEmpty()) {
34 moves++;
35 int levelSize = queue.size();
36
37 // Process all states at current level
38 for (int i = 0; i < levelSize; i++) {
39 String currentState = queue.poll();
40
41 // Convert string back to board for manipulation
42 setb(currentState);
43
44 // Generate all possible next states
45 for (String nextState : next()) {
46 // Check if we reached the target
47 if (nextState.equals(targetState)) {
48 return moves;
49 }
50
51 // Add unvisited states to queue
52 if (!visited.contains(nextState)) {
53 visited.add(nextState);
54 queue.offer(nextState);
55 }
56 }
57 }
58 }
59
60 // Target state unreachable
61 return -1;
62 }
63
64 /**
65 * Converts the current board to a string representation
66 * @return String representation of the board
67 */
68 private String gets() {
69 for (int row = 0; row < 2; row++) {
70 for (int col = 0; col < 3; col++) {
71 boardStringArray[row * 3 + col] = String.valueOf(board[row][col]);
72 }
73 }
74 return String.join("", boardStringArray);
75 }
76
77 /**
78 * Sets the board state from a string representation
79 * @param state String representation of the board
80 */
81 private void setb(String state) {
82 for (int row = 0; row < 2; row++) {
83 for (int col = 0; col < 3; col++) {
84 board[row][col] = state.charAt(row * 3 + col) - '0';
85 }
86 }
87 }
88
89 /**
90 * Finds the position of the empty cell (0) in the board
91 * @return Array containing [row, column] of the empty cell
92 */
93 private int[] find0() {
94 for (int row = 0; row < 2; row++) {
95 for (int col = 0; col < 3; col++) {
96 if (board[row][col] == 0) {
97 return new int[] {row, col};
98 }
99 }
100 }
101 return new int[] {0, 0}; // Default return (should never reach here)
102 }
103
104 /**
105 * Generates all possible next states from the current board state
106 * @return List of string representations of all possible next states
107 */
108 private List<String> next() {
109 // Find the empty cell position
110 int[] emptyPosition = find0();
111 int emptyRow = emptyPosition[0];
112 int emptyCol = emptyPosition[1];
113
114 // Direction vectors: up, right, down, left
115 int[] directions = {-1, 0, 1, 0, -1};
116 List<String> nextStates = new ArrayList<>();
117
118 // Try moving the empty cell in all 4 directions
119 for (int dir = 0; dir < 4; dir++) {
120 int newRow = emptyRow + directions[dir];
121 int newCol = emptyCol + directions[dir + 1];
122
123 // Check if the new position is within bounds
124 if (newRow >= 0 && newRow < 2 && newCol >= 0 && newCol < 3) {
125 // Swap empty cell with adjacent cell
126 swap(emptyRow, emptyCol, newRow, newCol);
127 // Add the new state to result
128 nextStates.add(gets());
129 // Swap back to restore original state
130 swap(emptyRow, emptyCol, newRow, newCol);
131 }
132 }
133
134 return nextStates;
135 }
136
137 /**
138 * Swaps two cells in the board
139 * @param row1 Row of first cell
140 * @param col1 Column of first cell
141 * @param row2 Row of second cell
142 * @param col2 Column of second cell
143 */
144 private void swap(int row1, int col1, int row2, int col2) {
145 int temp = board[row1][col1];
146 board[row1][col1] = board[row2][col2];
147 board[row2][col2] = temp;
148 }
149}
150
1class Solution {
2public:
3 int slidingPuzzle(vector<vector<int>>& board) {
4 // Convert initial board state to string representation
5 string startState = boardToString(board);
6 string targetState = "123450";
7
8 // If already solved, return 0
9 if (startState == targetState) return 0;
10
11 // Track visited states to avoid cycles
12 unordered_set<string> visited;
13 visited.insert(startState);
14
15 // BFS queue to explore states level by level
16 queue<string> bfsQueue{{startState}};
17 int moves = 0;
18
19 // BFS to find minimum moves
20 while (!bfsQueue.empty()) {
21 moves++;
22 int levelSize = bfsQueue.size();
23
24 // Process all states at current level
25 for (int i = 0; i < levelSize; i++) {
26 string currentState = bfsQueue.front();
27 bfsQueue.pop();
28
29 // Convert string back to board for generating next states
30 stringToBoard(currentState, board);
31
32 // Generate all possible next states
33 vector<string> nextStates = generateNextStates(board);
34
35 for (const string& nextState : nextStates) {
36 // Check if we reached the target
37 if (nextState == targetState) return moves;
38
39 // Add unvisited states to queue
40 if (!visited.count(nextState)) {
41 visited.insert(nextState);
42 bfsQueue.push(nextState);
43 }
44 }
45 }
46 }
47
48 // No solution found
49 return -1;
50 }
51
52private:
53 // Convert 2x3 board to string representation
54 string boardToString(vector<vector<int>>& board) {
55 string result = "";
56 for (int row = 0; row < 2; row++) {
57 for (int col = 0; col < 3; col++) {
58 result.push_back('0' + board[row][col]);
59 }
60 }
61 return result;
62 }
63
64 // Convert string representation back to 2x3 board
65 void stringToBoard(string state, vector<vector<int>>& board) {
66 for (int row = 0; row < 2; row++) {
67 for (int col = 0; col < 3; col++) {
68 board[row][col] = state[row * 3 + col] - '0';
69 }
70 }
71 }
72
73 // Generate all possible next states by sliding the empty tile
74 vector<string> generateNextStates(vector<vector<int>>& board) {
75 vector<string> nextStates;
76
77 // Find position of empty tile (0)
78 pair<int, int> emptyPos = findEmptyTile(board);
79 int emptyRow = emptyPos.first;
80 int emptyCol = emptyPos.second;
81
82 // Direction vectors: up, right, down, left
83 vector<int> directions = {-1, 0, 1, 0, -1};
84
85 // Try moving empty tile in all four directions
86 for (int dir = 0; dir < 4; dir++) {
87 int newRow = emptyRow + directions[dir];
88 int newCol = emptyCol + directions[dir + 1];
89
90 // Check if new position is valid
91 if (newRow >= 0 && newRow < 2 && newCol >= 0 && newCol < 3) {
92 // Swap empty tile with adjacent tile
93 swapTiles(emptyRow, emptyCol, newRow, newCol, board);
94 nextStates.push_back(boardToString(board));
95 // Swap back to restore original state
96 swapTiles(emptyRow, emptyCol, newRow, newCol, board);
97 }
98 }
99
100 return nextStates;
101 }
102
103 // Swap tiles at two positions on the board
104 void swapTiles(int row1, int col1, int row2, int col2, vector<vector<int>>& board) {
105 int temp = board[row1][col1];
106 board[row1][col1] = board[row2][col2];
107 board[row2][col2] = temp;
108 }
109
110 // Find the position of the empty tile (0) on the board
111 pair<int, int> findEmptyTile(vector<vector<int>>& board) {
112 for (int row = 0; row < 2; row++) {
113 for (int col = 0; col < 3; col++) {
114 if (board[row][col] == 0) {
115 return {row, col};
116 }
117 }
118 }
119 return {0, 0}; // Should never reach here in valid input
120 }
121};
122
1function slidingPuzzle(board: number[][]): number {
2 // Convert initial board state to string representation
3 let startState: string = boardToString(board);
4 const targetState: string = "123450";
5
6 // If already solved, return 0
7 if (startState === targetState) return 0;
8
9 // Track visited states to avoid cycles
10 const visited: Set<string> = new Set();
11 visited.add(startState);
12
13 // BFS queue to explore states level by level
14 const bfsQueue: string[] = [startState];
15 let moves: number = 0;
16
17 // BFS to find minimum moves
18 while (bfsQueue.length > 0) {
19 moves++;
20 const levelSize: number = bfsQueue.length;
21
22 // Process all states at current level
23 for (let i = 0; i < levelSize; i++) {
24 const currentState: string = bfsQueue.shift()!;
25
26 // Convert string back to board for generating next states
27 const currentBoard: number[][] = stringToBoard(currentState);
28
29 // Generate all possible next states
30 const nextStates: string[] = generateNextStates(currentBoard);
31
32 for (const nextState of nextStates) {
33 // Check if we reached the target
34 if (nextState === targetState) return moves;
35
36 // Add unvisited states to queue
37 if (!visited.has(nextState)) {
38 visited.add(nextState);
39 bfsQueue.push(nextState);
40 }
41 }
42 }
43 }
44
45 // No solution found
46 return -1;
47}
48
49// Convert 2x3 board to string representation
50function boardToString(board: number[][]): string {
51 let result: string = "";
52 for (let row = 0; row < 2; row++) {
53 for (let col = 0; col < 3; col++) {
54 result += board[row][col].toString();
55 }
56 }
57 return result;
58}
59
60// Convert string representation back to 2x3 board
61function stringToBoard(state: string): number[][] {
62 const board: number[][] = [[0, 0, 0], [0, 0, 0]];
63 for (let row = 0; row < 2; row++) {
64 for (let col = 0; col < 3; col++) {
65 board[row][col] = parseInt(state[row * 3 + col]);
66 }
67 }
68 return board;
69}
70
71// Generate all possible next states by sliding the empty tile
72function generateNextStates(board: number[][]): string[] {
73 const nextStates: string[] = [];
74
75 // Find position of empty tile (0)
76 const emptyPos: [number, number] = findEmptyTile(board);
77 const emptyRow: number = emptyPos[0];
78 const emptyCol: number = emptyPos[1];
79
80 // Direction vectors: up, right, down, left
81 const directions: number[] = [-1, 0, 1, 0, -1];
82
83 // Try moving empty tile in all four directions
84 for (let dir = 0; dir < 4; dir++) {
85 const newRow: number = emptyRow + directions[dir];
86 const newCol: number = emptyCol + directions[dir + 1];
87
88 // Check if new position is valid
89 if (newRow >= 0 && newRow < 2 && newCol >= 0 && newCol < 3) {
90 // Create a copy of the board to modify
91 const newBoard: number[][] = board.map(row => [...row]);
92
93 // Swap empty tile with adjacent tile
94 swapTiles(emptyRow, emptyCol, newRow, newCol, newBoard);
95 nextStates.push(boardToString(newBoard));
96 }
97 }
98
99 return nextStates;
100}
101
102// Swap tiles at two positions on the board
103function swapTiles(row1: number, col1: number, row2: number, col2: number, board: number[][]): void {
104 const temp: number = board[row1][col1];
105 board[row1][col1] = board[row2][col2];
106 board[row2][col2] = temp;
107}
108
109// Find the position of the empty tile (0) on the board
110function findEmptyTile(board: number[][]): [number, number] {
111 for (let row = 0; row < 2; row++) {
112 for (let col = 0; col < 3; col++) {
113 if (board[row][col] === 0) {
114 return [row, col];
115 }
116 }
117 }
118 return [0, 0]; // Should never reach here in valid input
119}
120
Time and Space Complexity
Time Complexity: O((m*n)! * m*n)
The sliding puzzle problem involves finding the shortest path from the initial board state to the target state "123450". This is essentially a BFS traversal through the state space graph.
- The total number of possible board states is
(m*n)!
wherem=2
andn=3
, giving us6! = 720
possible states - For each state, we need
O(m*n)
time to:- Convert between board and string representations (
gets()
andsetb()
both takeO(6)
time) - Find the position of 0:
O(m*n)
- Generate neighbors: up to 4 neighbors, each requiring
O(m*n)
operations for swapping and string conversion
- Convert between board and string representations (
- In the worst case, BFS visits all possible states
- Therefore, the total time complexity is
O(6! * 6) = O(720 * 6) = O(4320)
, which simplifies toO((m*n)! * m*n)
Space Complexity: O((m*n)!)
- The
vis
set can store up to(m*n)! = 6! = 720
unique states in the worst case - The BFS queue can also contain up to
O((m*n)!)
states in the worst case (though typically much less) - The temporary array
t
and board manipulations useO(m*n) = O(6)
space - The dominant factor is the visited set and queue, giving us
O((m*n)!)
space complexity
For this specific 2x3 puzzle, both complexities have constants: O(720 * 6)
for time and O(720)
for space, but in general form for an m×n puzzle, they are O((m*n)! * m*n)
and O((m*n)!)
respectively.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Inefficient State Representation and Comparison
Many implementations create new board objects or use nested lists directly as dictionary keys, which causes errors since lists are unhashable. Some try using tuples of tuples, which works but creates unnecessary overhead.
Problem Example:
# This will cause TypeError: unhashable type: 'list'
visited = {board} # Can't use list as set/dict key
# This works but is inefficient
visited = {tuple(tuple(row) for row in board)}
Solution: Convert the board to a string representation for efficient hashing and comparison. This reduces memory usage and speeds up lookups.
2. Not Restoring Board State After Generating Moves
A critical bug occurs when modifying the board to generate next states without restoring it, causing incorrect state generation in subsequent iterations.
Problem Example:
def get_next_states():
next_states = []
# Find zero position...
for dr, dc in directions:
if valid_position:
board[zero_row][zero_col], board[new_row][new_col] = board[new_row][new_col], board[zero_row][zero_col]
next_states.append(board_to_string())
# MISSING: Swap back to restore original state!
return next_states
Solution: Always swap back the tiles after recording the new state to maintain the board's integrity for generating other moves.
3. Processing States Level by Level Incorrectly
Failing to process all states at the current distance before incrementing the move counter leads to incorrect minimum move calculations.
Problem Example:
while queue: current = queue.popleft() moves += 1 # Wrong! Increments for each state, not each level # Process current state...
Solution: Use a for loop with range(len(queue))
to process exactly the states at the current level before incrementing moves:
while queue:
moves += 1
for _ in range(len(queue)): # Process entire level
current = queue.popleft()
# Generate and check next states...
4. Forgetting Edge Cases
Not checking if the initial state is already the target state, leading to unnecessary computation or incorrect results.
Solution: Always check if start_state == target_state
before starting BFS and return 0 immediately if true.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS
Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Want a Structured Path to Master System Design Too? Don’t Miss This!