Question

What is dynamic programming? How to solve a dynamic-programming problem?

Answer 1

Dynamic Programming:

It is an algorithmic paradigm which follows one rule, i.e. divide the complex problems into multiple subproblems and storing the results of those subproblems in order to reduce the computing of the redundant subproblems again.

Dynamic programming gives polynomial time solution to many problems whose solution are exponential time obtained from brute force method.

Steps to solve a dynamic programming problem:

Step 1: Identify whether the given problem is dynamic problem or not

Most of the problems needs quantitative result, i.e. maximize or minimize certain parameters or counting the number of ways to solve or obtain the result.

Also, dynamic programming problems requires to satisfy two of the major properties overlapping subproblems and optimal substructure property. If a problem satisfies the above mentioned properties, we can be sure of that the problem can be solve using dynamic programming.

Overlapping subproblems: Similar to divide and conquer, dynamic programming also divides the complex problem into multiple subproblems, and storing the result of those subproblems to reduce the computation cost. If there are no overlapping subproblems that can be identified, there is no point of solving complex problem into multiple subproblems, solving and storing the results of subproblems.

Optimal Substructure: A problem satisfies the property of optimal substructure, if a problem can be solved using the solutions of its multiple overlapping subproblems.

Step 2: Identify the state

State is defined as the particular instance or certain position of the problem. It can be obtained using set of parameters, i.e. how the change of value of certain parameters leads to change the state from previous state to next state.

Step 3: Identifying the relation among the states

This is the most important and critical state of the dynamic programming solution, it requires practice, and observational skills to identify the relation between the previous state and the next state, and how they are changing with certain change in the values of parameters.

Step 4: Memoization or tabulation of the state

This is also one of the important step, it requires storing the transition values(change in the parameters) which changes the previous state to next state, and using these transition values to solve other subproblems of the given problem.