Dynamic Programming (DP) is a powerful method in computer science for solving optimization problems, counting problems, and combinatorial problems. It’s a technique to solve problems by breaking them down into smaller subproblems. The solutions to these subproblems are then combined to solve the original problem, and thus allowing us to arrive at the desired solution more efficiently. In a way, it’s a kind of divide-and-conquer approach. However, what makes DP unique and more optimized is that it stores the solutions to subproblems to avoid re-computing them, which is also known as memoization.
The idea behind dynamic programming is mainly based on the following two entities:
1. **Bellman’s Principle of Optimality**: This principle states that an optimal policy (solution) has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy (solution) with regard to the state resulting from the initial decision.
2. **Overlapping Subproblems Property**: This property is the cornerstone of Dynamic Programming. A problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems. In simpler terms, if a recursive problem can be solved by solving smaller instances of identical problems, then we can use the DP technique.
The main process of Dynamic Programming can be broken down in the following steps:
1. **Step 1 (Analyzing subproblems)**: Break the problem down into smaller subproblems. These subproblems are not independent. In fact, the solution to one subproblem may depend on the solutions to various others.
2. **Step 2 (Memoization or "Remember your results")**: Once a subproblem has been solved, its solution is stored in a table so that it can be directly retrieved if needed again, thus avoiding re-computing the solution.
3. **Step 3 (Constructing an optimal solution to the problem)**: Using the solutions to the subproblems, solve the original problem.
A simple example of Dynamic Programming is the calculation of Fibonacci series where overlapping subproblems occur. Here, each number in the series is the sum of two preceding ones.
def Fibonacci(n):
if n<=0:
print("Incorrect input")
elif n==1:
return 0
elif n==2:
return 1
else:
return Fibonacci(n-1) + Fibonacci(n-2)Without dynamic programming, as the recursion depth increases, we solve the same subproblems repeatedly. To overcome this and increase efficiency, we save the result of each subproblem so we don’t need to compute it each time it’s needed.
def Fibonacci(n):
fibArray = [0,1]
while len(fibArray) < n+1:
fibArray.append(0)
if n<=1:
return n
else:
if fibArray[n-1] == 0:
fibArray[n-1] = Fibonacci(n-1)
if fibArray[n-2] == 0:
fibArray[n-2] = Fibonacci(n-2)
fibArray[n] = fibArray[n-2] + fibArray[n-1]
return fibArray[n] There’s no concrete DP formula, as its implementation very much depends on the problem at hand. Typically, the DP solution is based on a recurrence relation and the initial terms of the relation are solved in a bottom-up manner.