Dynamic programming (DP) is an algorithmic optimization technique over recursion when we cahe the results of subproblems so that we don’t have to recompute them again and again. The core idea is to avoid repeated work by remembering partial results.
It is important for a problem to have BOTH following characteristics in order to be eligible to be solved using DP technique.
There are following two different ways to store the values so that these values can be reused:
DP combines the correctness of compelete search and efficiency of greedy algorithms to reduce time complexity from exponetial to polynomial.
Usually creativity is required before we can recognize that a particular problem can be cast effectively as a dynamic program; and often subtle insights are necessary to restructure the formulation so that it can be solved effectively.
We should always start with a brute-force recursive solution, which is the best way to start solving any DP problem! Once we have a recursive solution then we will apply memoization and tabulation techniques.
More so than the optimization technique, DP provides a general framework for analyzing many problems:
DP is almost used everywhere which requires guaranteed optimal solution. It is heavily used in routing, graph problems, computer vision, computer networks, AI, machine learning etc.