Videos / DSA

Episode 20 of 22 · DSA, end to end

Dynamic programming: recursion with the answers written down

Chapters

1. Recursion with the answers kept0:00
2. Optimal substructure0:17
3. Where it actually fails0:34
4. Overlapping subproblems0:51
5. The recursion that does not1:12
6. The two questions1:30
7. Write the brute force1:48
8. Three hundred million2:06
9. Three lines, mechanically2:25
10. States times the work2:42
11. Only the reachable cells2:59
12. What top down costs3:15
13. Turn it inside out3:32
14. The order is the rule3:47
15. Two dimensions4:03
16. Keep only one row4:20
17. The direction trap4:36
18. Which one to write4:54
19. The label on the drawer5:11
20. What the index means5:28
21. What the value means5:45
22. Ending exactly at i6:01
23. When one index is short6:21
24. Getting the choices back6:39
25. Four names, one costume6:56
26. Knapsack7:13
27. Longest common subsequence7:30
28. Edit distance7:48
29. Where greedy visibly loses8:07
30. The same four rows8:25
31. An address, any shape8:42
32. From i to j9:00
33. Where the brackets go9:20
34. Children before parents9:40
35. One bit per element9:56
36. The four questions10:14
37. Write it down10:30

Dynamic programming: recursion with the answers written down. Here is a page of scratch work with every answer you have already computed written down the side. That is dynamic programming. It is not a clever trick and it is not a data structu

Mark as watchedSaved in this browser only.