Dynamic Programming: Solving Problems Optimally

dynamic programming n.w
1 / 94
Embed
Share

Gain insights into dynamic programming techniques for solving problems optimally, including iterative methods, divide-and-conquer strategies, and overcoming challenges such as overlapping subproblems and redundant work. Explore the concept of identifying dynamic programming problems and learn the steps involved in implementing dynamic programming solutions effectively.

  • Dynamic Programming
  • Algorithmic Techniques
  • Optimal Solutions
  • Overlapping Subproblems
  • Divide and Conquer
rayaanacharya
darc_688 Follow

Uploaded on | 3 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. DYNAMIC PROGRAMMING David Kauchak CS 140 Fall 2024

  2. Admin Assignment 3 Assignment 4

  3. Algorithmic "techniques" Iterative/incremental: solve problem of size n by first solving problem of size n-1. Divide-and-conquer: divide problem into independent subproblems. Solve each subproblem independently. Combine solutions to subproblem to create solution to the original problem.

  4. Dynamic programming Method for solving problems where optimal solutions can be defined in terms of optimal solutions to subproblems AND the subproblems are overlapping

  5. Fibonacci: a first attempt

  6. Running time Each call creates two recursive calls Each call reduces the size of the problem by 1 or 2: ? ? = ? ? 1 + ? ? 2 + ?(1) Creates a full binary of depth n (where the shortest leaf is at depth n/2) O(2n)

  7. Can we do better? Fib(n) Fib(n-2) Fib(n-1) Fib(n-4) Fib(n-2) Fib(n-3) Fib(n-3) Fib(n-4) Fib(n-4) Fib(n-5) Fib(n-5) Fib(n-6) Fib(n-3) Fib(n-4) Fib(n-5)

  8. A lot of repeated work! Fib(n) Fib(n-2) Fib(n-1) Fib(n-4) Fib(n-2) Fib(n-3) Fib(n-3) Fib(n-3) Fib(n-4) Fib(n-4) Fib(n-5) Fib(n-5) Fib(n-6) Fib(n-4) Fib(n-5)

  9. Identifying a dynamic programming problem The solution can be defined with respect to solutions to subproblems The subproblems created are overlapping, that is we see the same subproblems repeated

  10. Overlapping sub-problems divide and conquer dynamic programming

  11. Dynamic programming: steps recursive definition: use this to recursively define the value of an optimal solution DP solution: describe the dynamic programming table: size, initial values, order in which it s filled in, location of solution Analysis: analyze space requirements, running time

  12. Recursive definition Define a function and clearly define the inputs to the function The function definition should be recursive with respect to multiple subproblems pretend like you have a working function, but it only works on smaller problems Key: subproblems will be overlapping, i.e., inputs to subproblems will not be disjoint

  13. Recursive definition Fibonacci: F(n) = ?

  14. Recursive definition Fibonacci: F(n) = F(n-1) + F(n-2)

  15. DP solution The recursive solution will generally be top-down, i.e., working from larger problems to smaller DP solution: work bottom-up, from the smallest versions of the problem to the largest store the answers to subproblems in a table (often an array or matrix) to build bigger problems, lookup solutions in the table to subproblems

  16. DP solution F(n) = F(n-1) + F(n-2) What are the smallest possible values (subproblems)? To calculate F(n), what are all the subproblems we need to calculate? This is the table . How should we fill in the table?

  17. DP solution F(n) = F(n-1) + F(n-2) What are the smallest possible values (subproblems)? F(1) = 1, F(2) = 1 To calculate F(n), what are all the subproblems we need to calculate? This is the table . F(1) F(n-1) How should we fill in the table? F(1) F(n)

  18. DP solution Store the intermediary values in an array (fib)

  19. Analysis Space requirements? Running time?

  20. Analysis Space requirements: (n) Running time: (n)

  21. Counting binary search trees How many unique binary search trees can be created using the numbers 1 through n? 4 2 5 3 6 1

  22. Step 1: What is the subproblem? Assume we have a working function (call it T) that can give us the answer to smaller subproblems How can we use the answer from this to answer our question? How many options for the root are there? 1 2 3 n

  23. Subproblems i How many trees have i as the root?

  24. Subproblems i 1, 2, , i-1 i+1, i+2, , n ?

  25. Subproblems i 1, 2, , i-1 i+1, i+2, , n ? T(i-1) subproblem of size i-1

  26. Subproblems i 1, 2, , i-1 i+1, i+2, , n T(i-1) Number of trees for i+1, i+2, , i+n is the same as the number of trees from 1, 2, , n-i subproblem of size i-1

  27. Subproblems i 1, 2, , i-1 i+1, i+2, , n T(i-1) T(n-i) subproblem of size i-1 subproblem of size n-i

  28. Recursive definition i 1, 2, , i-1 i+1, i+2, , n T(i-1) T(n-i) Given solutions for T(i-1) and T(n-i) how many trees are there with i as the root?

  29. Recursive definition i 1, 2, , i-1 i+1, i+2, , n T(i-1) T(n-i) Trees with i as root = T(i-1) * T(n-i)

  30. Recursive definition Trees with i as root = T(i-1) * T(n-i) How many trees total? 1 2 3 n

  31. Recursive definition Trees with i as root = T(i-1) * T(n-i) = n = ( ) ( ) 1 * ( ) T n T i T n i 1 i 1 2 3 n

  32. A recursive implementation = n = ( ) ( ) 1 * ( ) T n T i T n i 1 i Like with Fibonacci, we re repeating a lot of work

  33. DP solution (from the bottom-up) = n = ( ) ( ) 1 * ( ) T n T i T n i 1 i What are the smallest possible subproblems? To calculate T(n), what are all the subproblems we need to calculate? This is the table . How should we fill in the table?

  34. DP solution (from the bottom-up) = n = ( ) ( ) 1 * ( ) T n T i T n i 1 i What are the smallest possible subproblems? T(0)=1, T(1) = 1 Why do we need T(0) and why is it 1?

  35. DP solution (from the bottom-up) = n = ( ) ( ) 1 * ( ) T n T i T n i 1 i What are the smallest possible subproblems? T(0)=1, T(1) = 1 1 Need to think carefully about base cases/edge cases

  36. DP solution (from the bottom-up) = n = ( ) ( ) 1 * ( ) T n T i T n i 1 i What are the smallest possible subproblems? T(0)=1, T(1) = 1 To calculate T(n), what are all the subproblems we need to calculate? This is the table . T(0) T(n-1) How should we fill in the table? T(0) T(n)

  37. DP solution (from the bottom-up)

  38. Fill in the first 4 values 0 1 2 3 4 5 n

  39. 1 1 0 1 2 3 4 5 n

  40. c[0]*c[1] + c[1]*c[0] 1 1 0 1 2 3 4 5 n

  41. 1 2 2 1 c[0]*c[1] + c[1]*c[0] 1 1 0 1 2 3 4 5 n

  42. 1 1 2 0 1 2 3 4 5 n

  43. 2 3 1 c[0]*c[2] + c[1]*c[1] + c[2]*c[0] 1 1 2 0 1 2 3 4 5 n

  44. 1 1 2 5 0 1 2 3 4 5 n

  45. 1 1 2 5 0 1 2 3 4 5 n

  46. 3: Analysis Space requirements? Running time?

  47. 3: Analysis Space requirements: (n) Running time: (n2)

  48. Subsequences For a sequence X = x1, x2, , xn, a subsequence is a subset of the sequence defined by a set of increasing indices (i1, i2, , ik) where 1 i1 < i2< < ik n X = A B A C D A B A B ABA?

  49. Subsequences For a sequence X = x1, x2, , xn, a subsequence is a subset of the sequence defined by a set of increasing indices (i1, i2, , ik) where 1 i1 < i2< < ik n X = A B A C D A B A B ABA

  50. Subsequences For a sequence X = x1, x2, , xn, a subsequence is a subset of the sequence defined by a set of increasing indices (i1, i2, , ik) where 1 i1 < i2< < ik n X = A B A C D A B A B ACA?

Related


No related presentations.

More Related Content