Deciding the state
Dynamic Programming problems are all about the state and its 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.
State:
A 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.
Example:
In our famous Knapsack problem, we define our state by two parameters index and weight i.e DP[index][weight]. Here DP[index][weight] tells us the maximum profit it can make by taking items from range 0 to index having the capacity of sack to be weight. Therefore, here the parameters index and weight together can uniquely identify a subproblem for the knapsack problem.
The first step to solving a Dynamic Programming problem will be deciding on a state for the problem after identifying that the problem is a Dynamic Programming problem. As we know Dynamic Programming 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.
Contact Us