Skip to main content

How to find DP

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)

Step 1 : How to classify a problem as a Dynamic Programming Problem?​

  • Typically, all the problems that require to maximize or minimize certain quantity or counting problems that say to count the arrangements under certain condition or certain probability problems can be solved by using Dynamic Programming.
  • All dynamic programming problems satisfy the overlapping subproblems property and most of the classic dynamic problems also satisfy the optimal substructure property. Once, we observe these properties in a given problem, be sure that it can be solved using DP.

Step 2 : Deciding the state​

DP problems are all about state and their transition. This is the most basic step which must be done very carefully because the state transition depends on the choice of state definition you make. So, let's see what do we mean by the term "state".

StateA state can be defined as the set of parameters that can uniquely identify a certain position or standing in the given problem. This set of parameters should be as small as possible to reduce state space

As we know DP is all about using calculated results to formulate the final result.

So, our next step will be to find a relation between previous states to reach the current state.

Step 3 : Formulating a relation among the states​

Let's think dynamically for this problem. So, first of all, we decide a state for the given problem. We will take a parameter n to decide state as it can uniquely identify any subproblem. So, our state dp will look like state(n). Here, state(n) means the total number of arrangements to form n by using 5 as elements.

Now, we need to compute state(n).

Step 4 : Adding memoization or tabulation for the state​

This is the easiest part of a dynamic programming solution. We just need to store the state answer so that next time that state is required, we can directly use it from our memory

References​

https://www.geeksforgeeks.org/solve-dynamic-programming-problem