The Dynamic Programming Manual
Mastering Efficient Solutions
Gábor László Hajba
This book is for sale at [Link]
This version was published on 2023-06-30
This is a Leanpub book. Leanpub empowers authors and publishers with the Lean Publishing
process. Lean Publishing is the act of publishing an in-progress ebook using lightweight tools and
many iterations to get reader feedback, pivot until you have the right book and build traction once
you do.
© 2023 Gábor László Hajba
Contents
Preface: Unleash the Power of Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . i
Part I: Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
What is Dynamic Programming? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Fundamental Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Advanced Dynamic Programming Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Dynamic Programming in Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Advanced Topics in Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Tips and Tricks for Efficient Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . 42
Conclusion and Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Part II: Dive into Dynamic Programming Chal-
lenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Fibonacci Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Fibonacci with Memoization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Last Digit of Fibonacci Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Longest Subsequence with Equal Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Longest Subarray with Equal 0s and 1s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Longest Common Subsequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Minimum Subset Sum Difference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Valid Parentheses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
CONTENTS
Minimum Number of Parentheses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Find the Element that Appears Once . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Find the Missing Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
Count Set Bits (Brian Kernighan’s Algorithm) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Generate All Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Power of Two . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Scalar Multiplication Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Topological Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Breadth-First Search (BFS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Depth-First Search (DFS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
Symmetric Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Lowest Common Ancestor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Trim a Binary Search Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Find Closest Value in BST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
Binary Tree Level Order Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
Climbing Stairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
Best Time to Buy and Sell Stock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
House Robber . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Coin Change . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
Coin Change 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Knapsack Problem (Bottom-Up) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
0/1 Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Knapsack with Duplicate Items . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Floyd-Warshall Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
Hamiltonian Path and Circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
N-Queens Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Sudoku Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Recover Binary Search Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
Edit Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
Dungeon Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
Cherry Pickup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
Travelling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
Part III: Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Proof of Optimal Substructure Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
Derivation of Memoization and Tabulation Techniques . . . . . . . . . . . . . . . . . . . . . . 202
Problem Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
Selecting the Right Data Structures for Dynamic Programming Efficiency . . . . . . . . . . 208
Preface: Unleash the Power of
Dynamic Programming
Why This Book?
Welcome to the world of Dynamic Programming! As an avid problem solver and programmer, I have
encountered numerous challenges where dynamic programming proved to be the most effective
solution. These problems appeared during my journey of expanding my knowledge and testing
myself with algorithmic puzzles. Surprisingly, they even crept into my day-to-day work.
Who Should Care?
Are you passionate about algorithms? Do you want to conquer challenges that become sluggish
with increasing input using brute force techniques? Whether you code in Java or Python, this book
will spark your creativity and provide valuable insights to enhance your code. Even if you work
with a different programming language, fear not! The principles of programming are universal, and
the examples in this book will help you grasp the essence of dynamic programming easily.
Bridging the Gap
I believe that there are like-minded individuals out there who yearn to tackle dynamic programming
problems but lack the proper guidance. This book aims to bridge that gap, providing a comprehensive
understanding of the topic and empowering you to approach dynamic programming problems with
confidence.
A Manual for Hands-On Learning
Prepare yourself for a hands-on experience! The emphasis of this book is on practical problem-
solving. While the background knowledge is essential, I want you to dive into the world of dynamic
programming by reading and analyzing example code. Throughout the book, you will discover
different solutions to the same problem, empowering you to adapt and find elegant solutions to
various programming challenges.
i
Preface: Unleash the Power of Dynamic Programming ii
Your Input Matters
This book is a labor of love and a result of self-publishing. With no hard deadlines, I am continually
adding problems and their solutions, crafting a valuable resource for you. If you encounter an
interesting problem and wish to explore my solution, I encourage you to reach out through the
book’s LeanPub web page. Let me know which problem you would like to see, and I will do my
best to incorporate it into the book promptly. As a purchaser, you will receive all updates and new
versions—your support matters!
However, I must mention that I am not a mathematician or a theoretical problem-solving expert.
There may be instances where I cannot solve your problem or it may require significant time to find
a solution.
Prerequisites: Let’s Get Started!
To fully grasp the concepts presented in this book, it is essential to have a basic understanding of
programming. I assume you are familiar with compiling and running code, and I do not impose
the use of a specific Integrated Development Environment (IDE). Feel free to work within the
environment of your choice.
Ask, and You Shall Receive
Throughout your journey with this book, if anything seems unclear or you encounter any confusion,
I encourage you to ask questions. Do not hesitate to reach out through LeanPub’s book discussion,
email, or social media channels. Your questions are essential, and seeking clarification ensures that
no part of your understanding is left incomplete.
Remember the wise words of one of my professors:
“Asking is not a shame. Not asking is a shame.”
A Compact and Informative Book
This book is intentionally designed to be concise yet packed with valuable information. Its length is
optimized to provide a price-value correspondence that exceeds your expectations. I hope you will
find immense value in the knowledge shared within these pages.
Preface: Unleash the Power of Dynamic Programming iii
Book Structure: A Path to Mastery
“The Dynamic Programming Manual” is your ultimate guide to mastering the art of dynamic
programming. This comprehensive book is divided into two parts, designed to provide you with
a complete understanding of the theory and practical implementation of dynamic programming.
In the first part, you will embark on a journey through the theoretical foundation of dynamic
programming. Starting with an introduction to Dynamic Programming, you will explore the history,
evolution, and applications of this powerful problem-solving technique. Gain insights into optimal
substructure, overlapping subproblems, and the memoization and tabulation techniques that form
the backbone of dynamic programming. Dive deep into time and space complexity analysis to
understand the efficiency of your solutions. Discover advanced techniques such as state space
reduction, bitmasking, bitwise operations, divide and conquer, and multidimensional dynamic
programming. With each chapter, you will expand your knowledge and build a solid foundation for
solving complex problems.
In the second part, you will put your theoretical knowledge into practice. Explore real-world
scenarios where dynamic programming shines, such as computer vision, natural language process-
ing, bioinformatics, financial modeling, and game theory. Learn how dynamic programming is
leveraged in these domains and gain insights into the unique challenges and approaches for each
application.
To further enhance your learning experience, the book provides a wealth of practical examples,
problem statements, and step-by-step solutions. You will find clear explanations, pseudocode, and
code examples in Java and Python, making it easier for you to grasp the concepts and implement your
own solutions. Whether you are a beginner seeking a comprehensive introduction or an experienced
programmer looking to sharpen your skills, “The Dynamic Programming Manual” has something
to offer.
With its detailed explanations, comprehensive coverage, and practical examples, this book serves as
your go-to resource for mastering dynamic programming. Whether you are preparing for coding
interviews, tackling challenging algorithmic problems, or seeking to optimize your code, this book
will equip you with the tools and techniques to tackle any dynamic programming challenge.
Get ready to unlock the full potential of dynamic programming and embark on a journey of problem-
solving mastery. Let “The Dynamic Programming Manual” be your companion in your quest for
efficient, elegant, and optimized solutions.
Why LeanPub?
I chose to publish this book on LeanPub for several reasons:
• Rapid Distribution: LeanPub enables me to distribute new parts and updates swiftly, ensuring
you have the latest content at your fingertips.
Preface: Unleash the Power of Dynamic Programming iv
• Eco-Friendly Approach: By offering only digital versions, we contribute to the preservation
of trees and reduce our environmental impact.
• Affordability: LeanPub’s digital format allows for cost-effective distribution, providing you
with a valuable resource at an affordable price. Plus, all updates and corrections are included!
Dynamic programming encompasses a vast array of problems, and I am committed to continually
adding new chapters to address different scenarios. My goal is to keep your brain engaged and
motivated, fostering your growth as a problem solver.
Distinguishing Features
You may wonder why I chose to write this book when numerous publications cover the same topic.
Allow me to highlight the unique aspects of “The Dynamic Programming Manual.” Traditional
publishers often limit your access to new versions, leaving you with outdated print books or
requiring you to purchase updated editions. In contrast, LeanPub ensures that you receive every
update and correction seamlessly, providing you with an exceptional learning experience.
In addition, while writing another book with a traditional publisher, Apress, I gained valuable
insights into the technical book production process. It can be rigorous, with strict deadlines and
numerous review phases. Yet, even with these efforts, updates and new editions remain a challenge.
I aim to deliver a different experience—one that surpasses the limitations of traditional publishing
and grants you a deep introduction to Dynamic Programming, covering both beginner and advanced
topics with practical examples.
Conclusion
Thank you for joining me on this exciting journey into the world of dynamic programming. As you
explore the book’s chapters, filled with engaging examples and insightful explanations, I hope you
will find inspiration and gain the knowledge and skills needed to excel in problem solving.
Remember, your questions and feedback are invaluable. Together, let’s unleash the power of
dynamic programming and embark on a transformational learning adventure!
Happy coding,
Gábor László Hajba
Part I: Theory
Welcome to the gateway of knowledge, where we unlock the theoretical foundations of dynamic
programming. In this captivating section, we delve into the core concepts and principles that lay
the groundwork for solving complex problems.
Unveiling the Hidden Patterns Prepare yourself for an exhilarating exploration into the hidden
patterns and structures that lie beneath dynamic programming problems. We unravel the enigmatic
nature of optimal substructure and overlapping subproblems, shedding light on their pivotal role in
the dynamic programming paradigm. By understanding these fundamental concepts, you will gain
a fresh perspective on problem-solving and embark on a transformative journey through the world
of algorithms.
Harnessing the Power of Memory Witness the alchemical fusion of technique and efficiency as
we uncover the secrets of memoization and tabulation. These remarkable techniques unlock the
true potential of dynamic programming, empowering you to store and retrieve valuable solutions
to subproblems. Marvel at the elegance of memoization, where the past becomes a treasure
trove of knowledge, and embrace the structured allure of tabulation, where tables hold the key to
optimization. Armed with these techniques, you will conquer complexity and elevate your problem-
solving prowess to new heights.
Navigating Time and Space Embark on a voyage through the intricacies of time and space
complexity analysis. Dive deep into the intricately woven fabric of computational efficiency as we
analyze the performance characteristics of dynamic programming algorithms. Explore the trade-
offs between time and space, unravel the mysteries of polynomial and exponential time complexity,
and chart a course towards optimal solutions. Armed with this knowledge, you will navigate the
vast sea of algorithms with confidence and precision.
Embracing the Code Experience the thrill of discovery as we demonstrate the practical application
of dynamic programming theory through captivating code examples. Immerse yourself in the world
of Java and Python as we bring the theoretical concepts to life, showcasing their potency and
versatility. Witness the intricate dance of logic and syntax, and unlock the door to elegant and
efficient solutions.
By delving into the theoretical underpinnings of dynamic programming, you will acquire the
essential tools and insights necessary to tackle the challenges that lie ahead. Prepare to be captivated
by the intricate tapestry of theory, as we equip you with the knowledge and understanding to
conquer the dynamic programming landscape. Let the journey begin!
What is Dynamic Programming?
Dynamic Programming is a powerful technique used in computer science and mathematics to solve
complex problems by breaking them down into simpler, overlapping subproblems. It provides an
efficient approach to find optimal solutions by storing and reusing solutions to subproblems, rather
than recomputing them repeatedly.
In essence, dynamic programming enables us to solve problems more efficiently by breaking them
into smaller, manageable parts and building up solutions incrementally. By leveraging the principle
of optimal substructure, where an optimal solution to a problem contains optimal solutions to its
subproblems, dynamic programming offers a systematic way to solve a wide range of problems.
History and Evolution of Dynamic Programming
The origins of dynamic programming can be traced back to the mid-20th century. The term
“dynamic programming” was coined by Richard Bellman in the 1950s while working on mathe-
matical optimization problems. However, the concept itself predates the term, with earlier works
by mathematicians like Euler and Hamilton addressing similar ideas.
Initially, dynamic programming found its application in the fields of operations research and
optimization, where it provided solutions to problems involving resource allocation, scheduling,
and network flow. Over time, its applicability expanded to various domains, including computer
science, algorithms, artificial intelligence, bioinformatics, and economics.
Applications of Dynamic Programming
Dynamic programming has proven to be a versatile and powerful technique, finding applications in
a wide range of problem domains. Some notable applications include:
• Algorithm Design: Dynamic programming is frequently used to solve algorithmic problems
efficiently. It provides solutions to challenges such as shortest paths, sequence alignment, graph
traversal, knapsack problems, and many more.
• Optimization: Dynamic programming plays a crucial role in optimizing resource allocation,
scheduling tasks, inventory management, and production planning. It allows for efficient
utilization of resources, minimizing costs, and maximizing performance.
• Bioinformatics: In the field of genetics and genomics, dynamic programming is used for
sequence alignment, DNA and protein folding, and analyzing genomic data. It aids in
understanding evolutionary relationships and identifying functional elements within genetic
sequences.
2
What is Dynamic Programming? 3
• Game Theory: Dynamic programming finds applications in game theory for solving games
with optimal strategies, such as chess, checkers, and other board games. It enables intelligent
decision-making and evaluating the best course of action at each step.
These are just a few examples of the extensive range of domains where dynamic programming has
made a significant impact. Its versatility and effectiveness in solving complex problems make it a
valuable tool for problem solvers across various disciplines.
Advantages and Limitations of Dynamic Programming
Dynamic programming offers several advantages that make it a preferred approach for solving
problems:
• Efficiency: By breaking down problems into smaller subproblems and reusing computed
solutions, dynamic programming significantly reduces computation time. It allows for solving
problems that would otherwise be computationally infeasible.
• Optimality: Dynamic programming guarantees finding optimal solutions by leveraging the
principle of optimal substructure. It ensures that the solution to a problem incorporates optimal
solutions to its subproblems, leading to an optimal overall solution.
• Simplicity: Although dynamic programming may initially seem complex, it provides a struc-
tured and systematic approach to problem-solving. Breaking down problems into subproblems
simplifies the solution process and enhances code modularity.
However, dynamic programming also has its limitations:
• Overlapping Subproblems: Not all problems exhibit overlapping subproblems, rendering
the dynamic programming approach less useful in those cases. Identifying the presence of
overlapping subproblems is crucial to determine the applicability of dynamic programming.
• Memory Usage: Dynamic programming algorithms often require additional memory to store
computed solutions for reuse. For problems with large input sizes, this can become a significant
constraint.
• Dependency on Problem Structure: The effectiveness of dynamic programming heavily relies
on the problem’s inherent structure and the ability to break it down into overlapping subproblems.
Some problems may not lend themselves well to dynamic programming techniques.
Overview of the Book
“The Dynamic Programming Manual” serves as a comprehensive guide to understanding and
applying dynamic programming techniques. Throughout this book, we will explore various
What is Dynamic Programming? 4
dynamic programming problems, providing detailed explanations and implementations in Java and
Python.
The chapters in this book are structured as follows:
1. Introduction to Dynamic Programming: This chapter introduces the concept of dynamic
programming, its history, applications, advantages, and limitations.
2. Problem 1: Each subsequent chapter focuses on a specific problem. We will present the
problem statement, explain the approach and solution, and provide implementations in both
Java and Python.
3. Problem 2
4. Problem 3
…
By working through these chapters, you will gain a solid understanding of dynamic programming
principles and enhance your problem-solving skills. Whether you are a seasoned programmer or
new to the world of dynamic programming, this book will provide valuable insights and practical
examples to strengthen your abilities.
Now, let’s dive into the world of dynamic programming and embark on an exciting journey of
problem solving and optimization!
Fundamental Concepts
In this chapter, we will explore the fundamental concepts that form the basis of dynamic pro-
gramming. Understanding these concepts is crucial to effectively solve problems using dynamic
programming techniques.
Optimal Substructure
Optimal substructure is a fundamental concept in dynamic programming that allows us to break
down complex problems into smaller, more manageable subproblems. It states that an optimal
solution to a larger problem can be constructed from optimal solutions to its smaller subproblems.
To illustrate the concept of optimal substructure, let’s explore a few examples implemented in both
Python and Java.
Example 1: Fibonacci Sequence
The Fibonacci sequence is a classic example that demonstrates optimal substructure. Each number
in the sequence is the sum of the two preceding numbers: 0, 1, 1, 2, 3, 5, 8, 13, and so on. We can
define the Fibonacci sequence recursively as follows:
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
}
5
Fundamental Concepts 6
In this example, the optimal substructure is evident. The Fibonacci number at index n is computed by
adding the Fibonacci numbers at indices n-1 and n-2. By breaking down the problem into smaller
subproblems (calculating the Fibonacci numbers at lower indices), we can obtain the solution for
larger indices.
However, this naive recursive implementation has exponential time complexity, as it recomputes
the same Fibonacci numbers multiple times. To optimize it using dynamic programming, we can
apply memoization or tabulation techniques to store the previously computed Fibonacci numbers
and avoid redundant calculations.
Example 2: Shortest Path in a Graph
Consider the problem of finding the shortest path in a graph from a source vertex to a destination
vertex. This is a well-known problem in graph theory and can be efficiently solved using dynamic
programming.
In Python, we can represent the graph as an adjacency matrix and use the Floyd-Warshall algorithm
to find the shortest path between all pairs of vertices:
def floyd_warshall(graph):
n = len(graph)
dist = [[float('inf') for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
dist[i][j] = graph[i][j]
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
In Java, we can implement the Floyd-Warshall algorithm similarly:
Fundamental Concepts 7
public class FloydWarshall {
public static int[][] floydWarshall(int[][] graph) {
int n = [Link];
int[][] dist = new int[n][n];
for (int i = 0; i < n; i++) {
[Link](graph[i], 0, dist[i], 0, n);
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = [Link](dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
return dist;
}
}
In this example, the optimal substructure is evident in the way the shortest path between pairs
of vertices is calculated. The algorithm iteratively considers intermediate vertices and determines
the shortest path based on the optimal solutions to subproblems. By building on these optimal
substructures, we can efficiently find the shortest path in a graph.
Summary
By examining these examples, we can observe how optimal substructure is utilized in dynamic
programming. It allows us to decompose complex problems into smaller, solvable subproblems and
construct the optimal solution iteratively. By avoiding redundant computations through techniques
like memoization and tabulation, we can improve the efficiency of our dynamic programming
solutions. Optimal substructure forms the foundation for developing effective and optimized
algorithms in both Python and Java.
Overlapping Subproblems
Overlapping subproblems is another key concept in dynamic programming. It refers to the
property of a problem where the set of subproblems required to solve the problem overlap or are
reused multiple times. This overlap allows us to optimize the computation by avoiding redundant
calculations and storing the results of subproblems for future use.
Fundamental Concepts 8
Let’s delve into a couple of examples implemented in Python and Java to better understand the
concept of overlapping subproblems.
Example 1: Fibonacci Sequence (Optimized)
In the previous example of the Fibonacci sequence, we saw how the naive recursive implementation
suffers from redundant calculations. To overcome this issue and take advantage of overlapping
subproblems, we can employ memoization, which involves caching the results of already computed
subproblems.
def fibonacci(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
import [Link];
import [Link];
public class Fibonacci {
public static int fibonacci(int n) {
Map<Integer, Integer> memo = new HashMap<>();
return fibonacciHelper(n, memo);
}
private static int fibonacciHelper(int n, Map<Integer, Integer> memo) {
if (n <= 1) {
return n;
}
if () {
[Link](n, fibonacciHelper(n-1, memo) + fibonacciHelper(n-2, memo));
}
return [Link](n);
}
}
Fundamental Concepts 9
In these optimized implementations, we introduce a memoization table (memo) to store the computed
Fibonacci numbers. Before calculating the Fibonacci number for a particular index, we check if it
exists in the memoization table. If it does, we directly retrieve the result from the table, avoiding
redundant recursive calls and significantly improving the efficiency of the algorithm.
Example 2: Binomial Coefficient
The binomial coefficient, often represented as “n choose k” (nCk), represents the number of ways to
choose k items from a set of n items. It can be computed using the formula:
C(n, k) = C(n-1, k-1) + C(n-1, k)
We can implement this computation using dynamic programming and exploiting the overlapping
subproblems property.
def binomialCoefficient(n, k):
table = [[0] * (k+1) for _ in range(n+1)]
for i in range(n+1):
for j in range(min(i, k)+1):
if j == 0 or j == i:
table[i][j] = 1
else:
table[i][j] = table[i-1][j-1] + table[i-1][j]
return table[n][k]
public class BinomialCoefficient {
public static int binomialCoefficient(int n, int k) {
int[][] table = new int[n+1][k+1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= [Link](i, k); j++) {
if (j == 0 || j == i) {
table[i][j] = 1;
} else {
table[i][j] = table[i-1][j-1] + table[i-1][j];
}
}
}
Fundamental Concepts 10
return table[n][k];
}
}
In these implementations, we use a 2D table (table) to store the intermediate results of binomial
coefficients.
By iteratively filling the table from smaller subproblems to larger ones, we can efficiently compute
the binomial coefficient for any given n and k. The table ensures that overlapping subproblems are
solved only once, and their results are reused when needed.
These examples demonstrate how overlapping subproblems are identified and leveraged in dynamic
programming. By avoiding redundant computations through memoization or tabulation techniques,
we can significantly improve the efficiency of our algorithms and solve complex problems efficiently.
Summary
In this section, we explored the concept of overlapping subproblems in dynamic programming. We
learned that overlapping subproblems occur when the same subproblems are encountered multiple
times in the computation of a problem’s solution. By leveraging this property, we can optimize our
algorithms by storing and reusing the results of already solved subproblems. Through examples
implemented in both Python and Java, we witnessed how memoization and tabulation techniques
can be used to address overlapping subproblems, resulting in more efficient and optimized solutions.
Understanding and identifying overlapping subproblems is crucial for designing effective dynamic
programming algorithms that can handle complex computational tasks with improved efficiency.
Memoization and Tabulation Techniques
Memoization and tabulation are two common techniques used in dynamic programming to optimize
the computation of solutions by storing and reusing the results of subproblems. These techniques
help avoid redundant calculations and improve the overall efficiency of dynamic programming
algorithms. Let’s explore each technique in detail and provide examples in both Python and Java.
Memoization Technique
Memoization involves caching the results of already computed subproblems in a memoization table
or cache. When a subproblem needs to be solved, its result is first checked in the memoization table.
If the result is present, it is directly returned from the table without recomputing. If the result is not
present, the subproblem is solved and its result is stored in the table for future use.
Here’s an example that demonstrates the memoization technique using the Fibonacci sequence
implemented in Python and Java:
Fundamental Concepts 11
def fibonacci(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
import [Link];
import [Link];
public class Fibonacci {
public static int fibonacci(int n) {
Map<Integer, Integer> memo = new HashMap<>();
return fibonacciHelper(n, memo);
}
private static int fibonacciHelper(int n, Map<Integer, Integer> memo) {
if (n <= 1) {
return n;
}
if () {
[Link](n, fibonacciHelper(n-1, memo) + fibonacciHelper(n-2, memo));
}
return [Link](n);
}
}
In these implementations, we introduce a memoization table (memo in Python and Map<Integer,
Integer> memo in Java) to store the computed Fibonacci numbers. Before calculating the Fibonacci
number for a particular index, we check if it exists in the memoization table. If it does, we directly
retrieve the result from the table, avoiding redundant recursive calls and significantly improving the
efficiency of the algorithm.
Tabulation Technique
Tabulation, also known as bottom-up dynamic programming, involves solving the subproblems in
a specific order and using a table or array to store the results of each subproblem. The table is filled
iteratively, starting from the base cases and progressing towards the final solution. By computing
Fundamental Concepts 12
the subproblems in a specific order, we can ensure that the results of the dependent subproblems are
already available when needed.
Let’s consider an example of calculating the binomial coefficient using the tabulation technique in
Python and Java:
def binomialCoefficient(n, k):
table = [[0] * (k+1) for _ in range(n+1)]
for i in range(n+1):
for j in range(min(i, k)+1):
if j == 0 or j == i:
table[i][j] = 1
else:
table[i][j] = table[i-1][j-1] + table[i-1][j]
return table[n][k]
public class BinomialCoefficient {
public static int binomialCoefficient(int n, int k) {
int[][] table = new int[n+1][k+1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= [Link](i, k); j++) {
if (j == 0 || j == i) {
table[i][j] = 1;
} else {
table[i][j] = table[i-1][j-1]
+ table[i-1][j];
}
}
}
return table[n][k];
}
}
In these implementations, we create a 2D table (table) to store the binomial coefficients for all
possible values of n and k. We fill the table iteratively using nested loops, computing each coefficient
based on the previously computed coefficients. By leveraging the tabulation technique, we avoid
redundant calculations and improve the efficiency of the algorithm.