What is the correct approach for dynamic programing? What are the essential prerequisite?

Question

Essential prerequisite to become a good problem solver in competitive programing.

Answer 1

Dynamic programming usually follows the same or a similar algorithmic approach to provide a linear solution to a problem and is often used in place of a recursive solution. It usually follows a pattern utilizing an array or array like structure for a top down or bottom up approach in which the first 2 elements are retrieved or set prior to entering into a loop that iterates over the array one time performing whatever calculations needed and setting any variable values needed. Upon finishing the loop usually the element at the end of the array or final calculation result is returned.

Here's an example of a dynamic programming bottom up solution to fibonacci. It eliminates the use of recursion and reduces the overall time complexity to O(n).

https://code.sololearn.com/cRC8VLqR9dKU/?ref=app

Answer 2

For competitive propgramming one should have a good knowledge of maths and the basic programming concepts like data structures and algorithms (rest you will automatically learn while learning)

For dynamic programming one should be good in recursion.