1 of 49

Dynamic Programming�(Smart Recursion)

​

​

By

Sarfraz

2 of 49

Shortest paths in DAGS, revisited

3 of 49

Shortest paths in DAGS, revisited

4 of 49

Shortest paths in DAGS, revisited

5 of 49

Longest paths in DAGS, revisited

For Longest paths what changes we should make???

6 of 49

Longest paths in DAGS, revisited

For Longest paths what changes we should make???

7 of 49

Catalan Number Computation

8 of 49

9 of 49

Quiz - Catalan Number Computation

THE Catalan SEQUENCE : ��1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ... 

Quiz - Write the C++ RECURSIVE code to compute N’th Catalan number?

10 of 49

Catalan Number - Application

Total Possible Parenthesization with n brackets are ???

Quiz 2 – Google 2 Other applications of Catalan numbers???

11 of 49

12 of 49

13 of 49

14 of 49

Catalan Numbers

  • Recurrence and Recursive Code

�

  • Memoization Solution
    • Top Down Approach

​

​

    • Bottom Up Approach –
      • Also called DP - solution

​

15 of 49

Tiling Problem

Tiling a 2×N rectangular floor with 1×2 and 2×1 tiles – In How many ways I can tile this floor?

​

16 of 49

Tiling Problem

Tiling a 2×N rectangular floor with 1×2 and 2×1 tiles – In How many ways I can tile this floor?

​

17 of 49

18 of 49

Fibonacci Numbers

Fib(N) = Fib(N-1) + Fib(N-2)�Fib(0) = 0�Fib(1) = 1

19 of 49

20 of 49

21 of 49

Fibonacci Numbers

  • Recurrence and Recursive Code

��

  • Memoization Solution
    • Top-Down Approach

��

    • Bottom Up Approach
    • Also called Dynamic Programming

FibTopDown

22 of 49

Largest Sum Contiguous Subarray (Stock Exchange Problem)

23 of 49

Largest Sum Contiguous Subarray

24 of 49

25 of 49

Largest Sum Contiguous Subarray (LSCS)

  • Inspiration:

“Any LSCS will end at any index”

26 of 49

Kadane’s Algorithm

27 of 49

Longest increasing subsequences

  • Increasing Sequence???

​

​

5

2

8

6

3

6

9

7

28 of 49

Longest increasing subsequences

  • Increasing Sequence???

​

​

5

2

8

6

3

6

9

7

29 of 49

Longest increasing subsequences

  • Increasing Sequence???

5

2

8

6

3

6

9

7

30 of 49

Longest increasing subsequences

Longest path from S to D correspond �to Longest Increasing subsequence

Green edges has weight 0 and blue �and black edges has weight 1.

31 of 49

Longest increasing subsequences

  • Increasing Sequence???

Longest path from S to D correspond �to Longest Increasing subsequence

32 of 49

Longest increasing subsequences

  • Increasing Sequence???

33 of 49

Longest increasing subsequences

34 of 49

Longest increasing subsequences

35 of 49

36 of 49

37 of 49

Rod Cutting Problem

​

​

​

​

​

  • There are how many possible ways to Cut the n length rod into pieces??? To maximize the profits?

38 of 49

Rod Cutting Problem

39 of 49

Rod Cutting Problem

40 of 49

Rod Cutting Problem

41 of 49

Rod Cutting Problem

42 of 49

Rod Cutting Problem (Time Complexity)

43 of 49

Rod Cutting Problem � (Top Down approach)

44 of 49

Rod Cutting Problem � (Top Down approach)

45 of 49

Rod Cutting Problem� (Bottom Up Approach)

46 of 49

Rod Cutting Problem� Book Keeping??

47 of 49

Rod Cutting Problem� Book Keeping??

48 of 49

Rod Cutting Problem� Book Keeping??

49 of 49

Thank You