DSA

Dynamic Programming

Dynamic Programming (DP) is a technique that solves some particular type of problems in Polynomial Time. An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, that is, T(n) = O(n^k) for some positive constant k.

Solve a DP problem

Steps to solve a DP -

Identify if it is a DP problem
Decide a state expression with least parameters
Formulate state relationship
Do tabulation (or add memoization)

Identify if it is a DP problem

Typically, all the problems that require maximizing or minimize certain quantities or counting problems.
All dynamic programming problems satisfy the overlapping subproblems property and most of the classic dynamic problems also satisfy the optimal substructure property.

Overlapping Subproblems

Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems. Dynamic Programming is mainly used when solutions of the same subproblems are needed again and again. So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no point storing the solutions if they are not needed again.

Optimal Substructure

A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.