DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Master the bottom-up DP approach with iterative table filling, understand computation order, and learn space optimization techniques.
What is Tabulation?
Tabulation is the iterative approach to DP. Instead of starting with the big problem and recursing down (top-down), you start with the smallest subproblems and build up to the answer. You fill a table (array) from the base cases forward, ensuring that when you compute dp[i], all values it depends on (dp[i-1], dp[i-2], etc.) are already computed.
The Pattern
Example
def solve_tabulation(n):
# 1. Create table
dp = [0] * (n + 1)
# 2. Fill base cases
dp[0] = base_value_0
dp[1] = base_value_1
# 3. Fill table iteratively
for i in range(2, n + 1):
dp[i] = transition(dp[i-1], dp[i-2], ...)
# 4. Return answer
return dp[n]
Fibonacci: Tabulation vs Memoization
Example
# Top-Down (Memoization)
@lru_cache(None)
def fib_memo(n):
if n <= 1: return n
return fib_memo(n-1) + fib_memo(n-2)
# Bottom-Up (Tabulation)
def fib_tab(n):
if n <= 1: return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
Both return the same result. Both are O(n) time, O(n) space. But tabulation has no recursion overhead and no stack overflow risk.
Space Optimization: The Key Advantage of Tabulation
With tabulation, you can often see that dp[i] only depends on the previous 1-2 values. This means you do not need the entire table — just a few variables!
Example
# O(n) space
def fib_table(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# O(1) space — only track last two values!
def fib_optimized(n):
if n <= 1: return n
prev2, prev1 = 0, 1
for i in range(2, n + 1):
curr = prev1 + prev2
prev2 = prev1
prev1 = curr
return prev1
This "rolling variable" technique is unique to tabulation. You cannot do this with memoization because recursive calls access arbitrary past states.
2D Tabulation Example: Unique Paths
Problem: Grid of m×n. Start at top-left, end at bottom-right. Can only move right or down. How many unique paths?
Example
def unique_paths(m, n):
# Full table: O(m*n) space
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
def unique_paths_optimized(m, n):
# Space optimized: O(n) — only need previous row!
prev_row = [1] * n
for i in range(1, m):
curr_row = [1] * n
for j in range(1, n):
curr_row[j] = prev_row[j] + curr_row[j-1]
prev_row = curr_row
return prev_row[n-1]
The insight: row i only depends on row i-1. So we only keep two rows at a time, reducing space from O(m×n) to O(n).
Determining Computation Order
The fill order must respect dependencies. Common patterns:
1D, left to right: dp[i] depends on dp[i-1], dp[i-2], etc.
Example
for i in range(n): dp[i] = f(dp[i-1], dp[i-2])
2D, row by row: dp[i][j] depends on dp[i-1][...] and dp[i][j-1]
Example
for i in range(m):
for j in range(n):
dp[i][j] = f(dp[i-1][j], dp[i][j-1])
2D, diagonal (gap-based): dp[i][j] depends on dp[i+1][j-1], dp[i][j-1] (interval DP)
Example
for length in range(2, n+1): # Gap/length
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = f(dp[i+1][j], dp[i][j-1], dp[i+1][j-1])
C++ Tabulation Example
Example
// Longest Increasing Subsequence - O(n²) tabulation
int LIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1); // Each element is LIS of length 1
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
Space Optimization Patterns
1D → O(1): When dp[i] depends only on fixed number of previous states
Example
# House robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
prev2, prev1 = 0, 0
for num in nums:
curr = max(prev1, prev2 + num)
prev2, prev1 = prev1, curr
2D → O(n): When dp[i][j] only depends on current and previous row
Example
# Knapsack: dp[i][w] depends on dp[i-1][w] and dp[i-1][w-wt[i]]
# Use 1D array, iterate capacity in reverse!
dp = [0] * (W + 1)
for i in range(n):
for w in range(W, wt[i]-1, -1): # Reverse to avoid using current row!
dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
The reverse iteration trick is crucial for 0/1 knapsack: iterating forward would use the updated (current row) values, effectively allowing items to be picked multiple times.
Tabulation vs Memoization Summary
| Aspect | Memoization (Top-Down) | Tabulation (Bottom-Up) |
|---|---|---|
| Style | Recursive | Iterative |
| Order | Determined by recursion | Must define explicitly |
| Space optimization | Difficult | Natural (rolling array) |
| Stack overflow | Risk for deep recursion | No risk |
| Subproblem coverage | Only solves needed subproblems | Solves all subproblems |
| Debugging | Harder (recursive stack) | Easier (print table) |
| Code style | More intuitive for some | More efficient typically |
Practical Tips
- Start with memoization to verify correctness, then convert to tabulation for optimization
- Always check dependencies before choosing fill order
- Space optimization is often the difference between AC and MLE in contests
- Print the DP table during debugging to verify transitions
- For 2D DP reduced to 1D, watch out for iteration direction (forward vs reverse)
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Tabulation (Bottom-Up Dynamic Programming).
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, dynamic, programming, tabulation
Related Data Structures & Algorithms Topics
Continue learning this concept
Dynamic ProgrammingDynamic Programming Interview ProblemsMaster essential DP interview problems: coin change, edit distance, rod cutting, climbing stairs, and house robber with clear approaches and solutions.Dynamic ProgrammingDynamic Programming FundamentalsUnderstand the core principles of dynamic programming: overlapping subproblems, optimal substructure, and how DP differs from divide-and-conquer and greedy approaches.Dynamic ProgrammingFibonacci with Dynamic ProgrammingSee how DP transforms Fibonacci from exponential O(2^n) naive recursion to O(n) memoization, O(n) tabulation, and O(1) space-optimized solution.Dynamic Programming0/1 Knapsack ProblemMaster the classic 0/1 Knapsack problem with 2D DP table construction, include/exclude decisions, solution traceback, and space optimization.Dynamic ProgrammingLongest Common Subsequence (LCS)Master the LCS problem with 2D DP table construction, backtracking for the actual subsequence, and its application in diff utilities.Dynamic ProgrammingLongest Increasing Subsequence (LIS)Solve LIS with O(n\u00b2) DP approach and the optimal O(n log n) patience sorting algorithm, with complete analysis and code.