I am an first-year computer science major master student at the University of Southern California
The core of dynamic programming: recursion with memorization. Breaking a big problem into small sub-problems and only computing each sub-problem once. Notice dynamic programming is an algorithm that will essentially search the entire solution space It’s usually helpful to think what’s the last step in your solution (top-down) and what sub-problem will it generate. But … Continue reading Dynamic Programming Revisit
Problem Statement: Giving m unsorted arrays, return the k smallest elements Method #1: Min-heap Method 1: Using bottom-up heap construction to build a min-heap, then pop the smallest element n times Complexity analysis: Time to construct min-heap: O(n) Time to extract min k times: O(k * lgn) Total time complexity: O(n + k * lgn) … Continue reading Full Analysis of Finding K Smallest in Sorted/Unsorted Arrays
Introduction Dynamic programming is closely related to divide & conquer and has far-ranging applications. They share the same idea of dividing a bigger and complicated question into smaller and easy-to-solve sub-problems of the same type. So both of them are based on recursion. The difference: In divide & conquer, sub-problems share the same type with … Continue reading Dynamic Programming
Follow My Blog
Get new content delivered directly to your inbox.