Dynamic Programming

What is Dynamic Programming?

Dynamic Programming (DP) is an optimization technique used to solve problems

by breaking them down into smaller, overlapping subproblems, solving each only
once, and using their solutions to build the answer for the overall problem. It
avoids redundant computations by storing solutions to subproblems in a table
(memoization or tabulation).

Two Main Properties of DP

1. Optimal Substructure:
A problem has optimal substructure if the optimal solution to the problem
can be obtained by combining optimal solutions to its subproblems.
Example: In the shortest path problem, the shortest path from node AAA
to node BBB includes the shortest path from AAA to an intermediate node
CCC, and from CCC to BBB.
2. Overlapping Subproblems:
A problem has overlapping subproblems if it repeatedly solves the same
subproblem in different parts of the recursion tree.
Example: Calculating Fibonacci numbers, where F(n)=F(n−1)+F(n−2)F(n)
= F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2), requires computing
F(n−1)F(n-1)F(n−1) and F(n−2)F(n-2)F(n−2), and these computations
overlap frequently.

Advantages of DP

1. Guarantees Optimal Solutions: If the problem has overlapping

subproblems and optimal substructure, DP guarantees the best solution.
2. Reduces Time Complexity: By storing the results of subproblems, DP
avoids recomputation, reducing time from exponential (O(2n)O(2^n)O(2n))
to polynomial (O(n2)O(n^2)O(n2)).
 3. Versatile: Applicable to a wide range of problems, including string
processing, optimization, and graph traversal.

Disadvantages of DP

1. High Space Complexity: Storing solutions for subproblems may require

large amounts of memory.
2. Time Consuming to Implement: Requires careful formulation of
recurrence relations and base cases.
3. Not Universally Applicable: DP only works when the problem satisfies
overlapping subproblems and optimal substructure.

Real-World Problems Solved Using DP

1. Financial Planning:
Allocating a budget over multiple months to minimize overspending or
maximize savings.
Why DP Works: Decisions for one month depend on previous months
(overlapping subproblems) and optimal allocation ensures overall savings
(optimal substructure).
2. Travel Itinerary Optimization:
Planning the cheapest route between cities while considering various costs
(tolls, fuel, time).
Why DP Works: Costs of visiting cities overlap (overlapping subproblems),
and each segment contributes to the optimal route (optimal substructure).
3. DNA Sequence Alignment (Bioinformatics):
Finding the minimum cost of transforming one DNA sequence into another
through insertions, deletions, or substitutions.
Why DP Works: Subproblem results for smaller sequence segments
contribute to the global alignment solution.

Real-World Problems Where DP Fails

 1. Fractional Knapsack Problem:
DP fails because items can be taken fractionally, which creates infinite
subproblems.
Why DP Fails: The problem lacks discrete overlapping subproblems.
2. Task Scheduling Without Dependencies:
DP is unnecessary when tasks don’t depend on each other. Greedy
algorithms are faster and sufficient.
Why DP Fails: Greedy is more efficient for independent tasks.

Top Technical Problems Solved by DP

1. 0/1 Knapsack Problem:

Find the maximum value that can be obtained by selecting items without
exceeding capacity.
Why DP Works: Overlapping subproblems arise in considering subsets of
items, and solutions combine optimally.
2. Longest Common Subsequence (LCS):
Find the longest sequence common to two strings.
Why DP Works: Results for smaller substrings contribute to the solution
for larger substrings.
3. Matrix Chain Multiplication:
Find the most efficient way to multiply matrices to minimize scalar
multiplications.
Why DP Works: Partial results for submatrices overlap and combine to
form the global solution.
4. Shortest Path Problems:
○ Bellman-Ford Algorithm for graphs with negative weights.
○ Floyd-Warshall for all-pairs shortest path.
Why DP Works: Paths overlap across nodes, and subpaths
combine to find the shortest route.
5. Palindrome Partitioning:
Determine the minimum cuts needed to partition a string into palindromes.
Why DP Works: Results for substrings are reused to minimize cuts.

Machine Learning Algorithms Using DP

 1. Hidden Markov Models (HMMs):
○ Viterbi Algorithm: Finds the most likely sequence of hidden states.
Why DP Works: Probabilities for smaller sequences overlap and are
reused.
2. Sequence Alignment:
○ Used in bioinformatics and NLP for comparing sequences (e.g.,
DNA, sentences).
Why DP Works: Smaller subsequences’ alignment contributes to
the global solution.
3. Reinforcement Learning:
○ Value Iteration: Solves Markov Decision Processes by iteratively
updating values of states.
Why DP Works: Overlapping subproblems exist in computing value
functions.

How to Analyze If a Problem Can Be Solved by DP

1. Check for Overlapping Subproblems:

○ Are the same subproblems being solved multiple times?
○ Example: Fibonacci sequence.
2. Check for Optimal Substructure:
○ Can the problem be divided into smaller subproblems whose
solutions combine to solve the original problem?
○ Example: Shortest paths in graphs.
3. Formulate Recurrence Relation:
○ Write a mathematical relation for the problem that relates smaller
subproblems to the overall solution.
4. Space Optimization:
○ Identify if the solution can be optimized for memory (e.g., reduce 2D
arrays to 1D).

Top Exam Conceptual Questions Asked on DP (with Solutions)

1. Fibonacci Numbers:
 ○ Question: How does DP improve the computation of Fibonacci
numbers?
○ Solution: Use a table to store results of previously computed
Fibonacci numbers. Time complexity reduces from
O(2n)O(2^n)O(2n) to O(n)O(n)O(n).
2. Longest Palindromic Subsequence:
○ Question: Find the length of the longest palindromic subsequence in
a string.
○ Solution: Use DP to check for matching characters and recursively
build the solution.
3. Subset Sum Problem:
○ Question: Given a set of integers, determine if a subset exists with a
given sum.
○ Solution: Use DP to iteratively check subsets of increasing sizes.
4. Rod Cutting Problem:
○ Question: Maximize the profit from cutting a rod of length nnn.
○ Solution: Use DP to evaluate profits for smaller cuts and combine
results.

Top Interview Questions on DP

1. Climbing Stairs:
○ Question: Find the number of ways to climb nnn stairs, taking 1 or 2
steps at a time.
○ Solution: dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] +
dp[i-2]dp[i]=dp[i−1]+dp[i−2].
2. House Robber Problem:
○ Question: Maximize the money robbed without alerting police (no
adjacent houses).
○ Solution: dp[i]=max⁡(dp[i−1],dp[i−2]+nums[i])dp[i] = \max(dp[i-1],
dp[i-2] + nums[i])dp[i]=max(dp[i−1],dp[i−2]+nums[i]).
3. Edit Distance:
○ Question: Find the minimum operations required to convert one
string into another.
○ Solution: Use DP to calculate costs for inserting, deleting, or
replacing characters.
Difference Between DP and Greedy

1. Decision-Making:
○ DP: Considers all possibilities and stores solutions to subproblems.
○ Greedy: Makes a local optimal choice at each step.
2. Optimal Substructure:
○ Both DP and greedy require this property.
○ Greedy also requires the greedy-choice property, which DP does
not.
3. When to Use:
○ Use DP when overlapping subproblems exist and greedy fails (e.g.,
0/1 knapsack).
○ Use greedy for simpler problems with a clear local-to-global optimal
solution (e.g., activity selection).

This detailed explanation covers all your questions about Dynamic

Programming, emphasizing clarity and real-world relevance.
Dynamic Programming (DP) Overview

Dynamic Programming (DP) is an optimization technique used to solve complex

problems by breaking them down into smaller subproblems, solving each
subproblem just once, and storing the results to avoid redundant computation.

Two Main Properties of Dynamic Programming

1. Optimal Substructure:

○ A problem has optimal substructure if an optimal solution to the

problem can be built from optimal solutions to its subproblems.
○ Example: In the shortest path problem, the shortest path to a
destination node involves the shortest paths to intermediate nodes.
2. Overlapping Subproblems:

○ A problem has overlapping subproblems if the same subproblem is

solved multiple times during recursion.
○ Example: Fibonacci numbers where F(n)=F(n−1)+F(n−2)F(n) =
F(n-1) + F(n-2); the subproblems F(n−1)F(n-1) and F(n−2)F(n-2)
overlap repeatedly.

Advantages of Dynamic Programming

1. Guarantees Optimal Solutions: If applicable, DP ensures the globally

optimal solution.
2. Efficient for Overlapping Subproblems: Avoids recomputation by storing
results in a table (memoization or tabulation).
3. Applicable to a Wider Range of Problems: Works for problems where
greedy algorithms fail.

Disadvantages of Dynamic Programming

1. High Space Complexity: Requires memory to store intermediate results,

which can be large.
 2. Slower Than Greedy for Certain Problems: Since it considers all
possible subproblem solutions, it can be slower than greedy.
3. Problem-Specific: Requires careful problem formulation to apply the
technique.

Real-World Scenarios Where DP Works

1. Planning Your Monthly Budget:

○ Allocate a budget across different categories to maximize savings or

minimize overspending.
○ Example: Spending in one category affects how much you can
spend in another.
2. Road Trip Planning:

○ Finding the cheapest route across multiple cities considering tolls,

gas, and time.
○ Why DP Works: Each route is dependent on costs of smaller
segments, and overlapping subproblems exist (revisiting cities).
3. Project Scheduling with Dependencies:

○ Organizing tasks when some depend on others and have specific

durations (e.g., Gantt charts in project management).
○ Why DP Works: Solving dependencies iteratively builds an optimal
schedule.
4. Stock Trading:

○ Deciding when to buy, sell, or hold stocks to maximize profit over

time.
○ Why DP Works: Profits depend on previous day’s decisions,
overlapping subproblems exist.

Real-World Scenarios Where DP Fails

 1. Packing for a Trip (Fractional Knapsack):

○ DP cannot handle cases where items can be taken fractionally since

it would require infinite divisions.
○ Why DP Fails: Problem lacks discrete overlapping subproblems.
2. Daily Task Scheduling:

○ Selecting tasks that don’t overlap (e.g., scheduling meetings).

○ Why DP Fails: Greedy algorithms are faster and work because each
choice is independent of future tasks.

Top Technical Problems Solved by DP

1. Knapsack Problems:
○ 0/1 Knapsack: Find the maximum value by selecting items without
exceeding capacity.
○ Subset Sum: Determine if a subset with a given sum exists.
2. String Problems:
○ Longest Common Subsequence (LCS).
○ Longest Palindromic Substring.
3. Graph Problems:
○ Shortest Path in Graphs (e.g., Bellman-Ford Algorithm).
○ All-Pairs Shortest Path (e.g., Floyd-Warshall Algorithm).
4. Game Theory:
○ Optimal strategies for games like Tic-Tac-Toe or chess endgames.
5. Matrix Chain Multiplication:
○ Minimizing the number of scalar multiplications.

Machine Learning Algorithms Using DP

1. Hidden Markov Models (HMM):

○ Viterbi Algorithm for finding the most likely sequence of hidden
states.
2. Sequence Alignment:
 ○ Dynamic programming is used in bioinformatics for DNA and protein
sequence alignment.
3. Value Iteration:
○ Used in Reinforcement Learning for solving Markov Decision
Processes (MDPs).

Top Exam Conceptual Questions on DP

1. Fibonacci Numbers:

○ Explain how DP optimizes the computation of Fibonacci numbers.

○ Solution: Use a table to store results of previous calculations,
reducing exponential time complexity to O(n)O(n).
2. Longest Common Subsequence (LCS):

○ Find the LCS of two strings using DP.

○ Solution: Build a 2D table to store results for every pair of prefixes.
3. 0/1 Knapsack Problem:

○ Derive the recurrence relation for solving the 0/1 knapsack problem.
○ Solution: dp[i][w]=max⁡(dp[i−1][w],dp[i−1][w−wt[i]]+val[i])dp[i][w] =
\max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i]).
4. Matrix Chain Multiplication:

○ Explain how DP minimizes matrix multiplication cost.

○ Solution: Use DP to store the cost of multiplying subsets of
matrices.

Top Interview Questions on DP

1. Climbing Stairs:

○ Given nn stairs, each time you can climb 1 or 2 steps. How many
distinct ways can you climb to the top?
 ○ Solution: Use the recurrence dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] +
dp[i-2].
2. Rod Cutting Problem:

○ Given a rod of length nn and prices for each piece, find the
maximum revenue obtainable.
○ Solution: Use DP to evaluate all possible cuts and store maximum
values.
3. Minimum Edit Distance:

○ Find the minimum operations (insert, delete, replace) to convert one

string into another.
○ Solution: Build a DP table where dp[i][j]dp[i][j] represents the cost
for substrings of length ii and jj.
4. House Robber Problem:

○ Given an array of non-negative integers representing the amount of

money at each house, find the maximum amount without robbing
adjacent houses.
○ Solution: dp[i]=max⁡(dp[i−1],dp[i−2]+nums[i])dp[i] = \max(dp[i-1],
dp[i-2] + nums[i]).

Difference Between Greedy and DP

1. Decision-Making:

○ Greedy makes decisions step-by-step without revisiting.

○ DP solves all subproblems and combines results for the global
optimum.
2. Applicability:

○ Greedy works when the greedy-choice property and optimal

substructure hold.
○ DP works when optimal substructure and overlapping
subproblems exist.
 3. Examples:

○ Greedy: Fractional Knapsack, Prim’s Algorithm.

○ DP: 0/1 Knapsack, Matrix Chain Multiplication.

How to Analyze a Problem for DP

1. Check for Overlapping Subproblems:

○ Are there smaller subproblems being solved repeatedly?

○ Example: Fibonacci numbers.
2. Check for Optimal Substructure:

○ Can the problem be solved using solutions to smaller subproblems?

○ Example: Shortest paths in graphs.
3. Formulate Recurrence Relation:

○ Derive a mathematical relation to solve the problem iteratively or

recursively.
4. Space Optimization:

○ Identify if the DP solution can be optimized for space (e.g., reduce a

2D table to 1D).

Both greedy algorithms and dynamic programming are powerful tools.

Understanding their properties, use cases, and limitations allows you to choose
the right technique for a given problem.