Things to Know before starting Dynamic Programming
1] Recursion – DP mostly uses solving problems recursively. That you should have a hands-on experience with recursion.
2] Basic Data Structures – You should be clear on the fundamentals of data structures like Arrays, Stacks, Trees, Linked lists, etc.
3] Sorting Algorithms – Familiarize yourself with sorting algorithms like the Bubble sort, Insertion sort, and Merge sort. These sorting algorithms are mostly used in dynamic programming.
4] Graph Algorithms – You should know basic graph algorithms like Breadth First Search (BFS) and depth First Search (DFS).
5] Greedy Algorithms – Few of the DP problems can be solved by greedy algorithms, so you must how the Greedy algorithm works.
6] Divide and Conquer – You should be familiar with algorithms like Merge sort, and Quicksort which use divide and conquer techniques to solve the problems. This technique is closely related to dynamic programming.
7[ Memorization – To optimize the recursive solutions this technique is used. Basically, memorization involves storing the results of expensive function calls and reusing them when the same inputs occur again.
8] Backtracking – A few DP problems involve backtracking to explore all possible solutions. You should be familiar with the problems like N-Queens problem or the traveling salesman problem.
9] Binary Search – It’s important to know the implementation of binary search because it is a fundamental technique in many DP problems.
10] DP Concepts – Must know some core concepts like optimal substructure, overlapping, subproblems, and how to formulate problems as recursive relations.
11] Mathematical concepts – Master the concepts of Permutation, Combinations, and combinatorics, these are mostly used in DP
12] Complexity Analysis – Familiarizing with time and space complexity analysis will help you assess the efficiency of your DP solutions.
13] DP patterns – Familiarize yourself with DP patterns like bottom-up(tabulation), and top-down(memorization), and also need to recognize when to use those.
14] Practice – Solve a variety of coding problems on popular platforms like Leetcode, Codeforces, HackerRank, and Codechef to get better hands-on experience in coding and problem patterns.
