Scribd
Upload
13 views19 pages

DP 202

The document discusses optimization problems, specifically focusing on dynamic programming techniques such as memoization and tabulation. It provides a code example for generating the Fibonacci series and outlines key concepts of dynamic programming, including optimal substructure and overlapping subproblems. Additionally, it lists common dynamic programming problems like the Fibonacci sequence, longest common subsequence, knapsack problem, and matrix chain multiplication.

Uploaded by

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

DP 202

The document discusses optimization problems, specifically focusing on dynamic programming techniques such as memoization and tabulation. It provides a code example for generating the Fibonacci series and outlines key concepts of dynamic programming, including optimal substructure and overlapping subproblems. Additionally, it lists common dynamic programming problems like the Fibonacci sequence, longest common subsequence, knapsack problem, and matrix chain multiplication.

Uploaded by

urvashipadhiyar1947
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 19

An optimization problem involves finding the best solution

from a set of feasible solutions, often under certain


constraints. The goal is to either maximize or minimize a
particular objective function.
Divide & Conquer
Dynamic
Programming
Fibonacci
Series
#include <stdio.h>
The code uses a function named fibonacci to
// Function to print the Fibonacci series print the Fibonacci series. The function takes an
void fibonacci(int n) integer n as input, which represents the number
{ of terms in the series.
int a = 0;
int b = 1; The variables a and b are used to store the
int temp; previous two numbers in the series, and the
variable temp is used to store the next number
printf("%d %d ", a, b); in the series.

for (int i = 3; i <= n; i++) The function uses a for loop to iterate from 3 to
{ n, and in each iteration, it calculates the next
temp = a + b; number in the series using the formula temp = a
a = b; + b. The function then updates the values of a
b = temp; and b using the assignments a = b and b =
printf("%d ", b); temp.
}
}` Finally, the function prints the next number in
the series using the statement printf("%d ", b).
int main() { Enter the number of terms: 10
Fibonacci series: 0 1 1 2 3 5 8 13 21 34
int n;

printf("Enter the number of


terms: ");
scanf("%d", &n);

printf("Fibonacci series: ");


fibonacci(n);

return 0;
}
Key Concepts of Dynamic Programming in Design and Analysis of Algorithms (DAA)
1. Optimal Substructure:
○ This means that the solution to a given problem can be obtained by combining the optimal
solutions to its subproblems. It's a hallmark of problems suited for dynamic programming.
2. Overlapping Subproblems:
○ Dynamic programming is efficient because it stores the solutions to subproblems in a table
(usually an array ) and reuses these solutions when the same subproblem arises again.
○

Memoization:
● This involves storing the results of expensive function calls and reusing them when the
same inputs occur again. It's typically implemented using a top-down approach with
recursion.

Tabulation:

● This is the opposite of memoization. It uses a bottom-up approach, starting with the
simplest subproblems and combining them to solve larger problems, usually with iterative
loops.
1. Fibonacci Sequence (Basic DP Example)

● Problem: Find the nthn^{th}nth Fibonacci number.


● Approach: Store computed values in an array to avoid recomputation.
● Time Complexity: O(n)

.2. Longest Common Subsequence (LCS)


● Problem: Find the longest common subsequence of two strings.
● Time Complexity: O(m×n)O(m \times n)O(m×n) (for two strings of length m and n)
3. Knapsack Problem (0/1 Knapsack)
● Problem: Given n items, each with a weight and a value, find the maximum value that can be
obtained with a weight limit W.

4. Matrix Chain Multiplication

● Problem: Given a sequence of matrices, find the minimum number of scalar multiplications needed to
multiply them.
Examples of Dynamic Programming

You might also like