DYNAMIC_________________________PROGRAMMING.pptx

DYNAMIC_PROGRAMMING

1. DYNAMIC PROGRAMMING Presented By Group : 4 Group Members : Md.Nazmus Shakib -220320852 Tanvin Sadik Dhrubo -220320860 Khan Waziur Rahman -220320861 Arghya Saha -200120456

2. Introduction to Dynamic Programming Dynamic Programming is a method for solving complex problems by breaking them down into simpler sub problems. It is applicable where the problem can be divided into overlapping subproblems and has optimal substructure. It is also known as divide and conquer technique

3. Why We Choose Dynamic Programming Over Greedy Method? Dynamic programming (DP) is often preferred over the greedy method for solving optimization problems where future decisions are affected by earlier ones. In greedy algorithms, the approach is to make the locally optimal choice at each stage in hopes of finding the global optimum. However, this doesn't always lead to the best solution for all problems, as greedy methods may miss key subproblems or fail to consider how earlier decisions affect the later ones.

4. Dynamic programming approaches

5. Dynamic Programming Approaches

6. Memoization vs Tabulation

7. Memoization F4 F2 F1 F0 F1 F1 F0 F2 F3 1 1 2 3 F0 F1 F2 F3 F4 F = Time Complexity= O(n) Fn F(n-2) F(n-1) Global Array

8. Memoization The Fibonacci sequence is defined as: F(n)=F(n−1)+F(n−2) with base cases: F(0)=0, F(1)=1 Function Of fibonacci series : int fib(int n){ if (n<=1) { return n; } else { return fib(n-2) + fib(n-1); } } Top-down approach

9. Tabulation Function Of fibonacci series: int fib(int n){ if (n<=1) { return n; F[0]=0;F[1]=1; } for(int i =2; i <=n; i ++){ F[ i ] = F[i-2]+F[i-1]; } return F[n]; } 1 1 2 3 F0 F1 F2 F3 F4 F = Time Complexity= O(n) Global Array Bottom-up approach F1 F0 F2

10. Key Concepts of Dynamic Programming

11. Steps to Apply Dynamic Programming

12. Advantages of Dynamic Programming

13. Disadvantages

14. THANK YOU!