Scribd
Upload
13 views2 pages

Dynamic Programming - General Method

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into smaller overlapping subproblems, storing results to improve efficiency. Key concepts include optimal substructure and overlapping subproblems, with two main approaches: Top-Down (Memoization) and Bottom-Up (Tabulation). An example is generating the Fibonacci sequence, where DP avoids redundant calculations by storing computed values.

Uploaded by

muhammadsuhail200511
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
13 views2 pages

Dynamic Programming - General Method

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into smaller overlapping subproblems, storing results to improve efficiency. Key concepts include optimal substructure and overlapping subproblems, with two main approaches: Top-Down (Memoization) and Bottom-Up (Tabulation). An example is generating the Fibonacci sequence, where DP avoids redundant calculations by storing computed values.

Uploaded by

muhammadsuhail200511
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Dynamic Programming – general method

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


breaking them down into smaller overlapping subproblems and solving each subproblem only
once, storing the results for future use.

• This avoids redundant computations and improves efficiency, making DP useful for solving
problems with optimal substructure and overlapping subproblems.

Key Concepts:

• Optimal Substructure – A problem exhibits optimal substructure if its optimal solution can be
constructed from the optimal solutions of its subproblems.

• Overlapping Subproblems – The problem can be broken down into smaller subproblems that
are reused multiple times.

Approaches:

• Top-Down (Memoization): Recursively solve subproblems and store results to avoid redundant
calculations.

• Bottom-Up (Tabulation): Solve subproblems iteratively and store results in a table to build up
the solution.

Example: Apply memorization and Tabulation method to generate first ‘n’ terms of
Fibonacci series

Fibonacci Sequence: Instead of recalculating Fibonacci numbers recursively, DP stores already


computed values to avoid redundant computations.

Top-Down (Memoization):

Algorithm fib(n)
{
if (n<=1) then
{
return n;
}
if (arr[n]!=-1 )then
{
return arr[n];
}
arr[n]=fib(n-1)+fib(n-2);
return arr[n]
}
Algorithm main()
{
n=10
for i = 0 to n do
{
arr[i]=-1;
}
write fib(n);
}

Bottom-Up (Tabulation):

Algorithm fib( n)
{
if (n<=1)
{
return n;
}
int arr[n+1];
arr[0]=0;
arr[1]=1;
for i=2 to n do
{

arr[n]=arr(n-1)+arr(n-2);

}
return arr[n]
}

You might also like