Introduction to Dynamic programming

You will learn about dynamic programming in this tutorial using a beginner's approach. Why DP is so important for writing effective code? And two essential techniques for solving dynamic problems. Let's start with a great and powerful technique for writing beautiful and efficient code.

What is dynamic programming?

Dynamic programming is a method of solving problems by breaking them down into smaller, overlapping subproblems. The solutions to these subproblems are then stored in a table so that they can be reused instead of recalculating them each time they are needed. This can greatly reduce the time and space complexity of a problem, making it much more efficient to solve.

Why we need to know about dynamic programming technic?

Many problems that seem intractable at first glance can be solved relatively easily with dynamic programming. This is because dynamic programming breaks down a problem into smaller, overlapping subproblems, and stores the solutions to these subproblems in a table, making it possible to reuse them instead of recomputing them each time they are needed.

Dynamic programming can often be used to find optimal solutions to problems, rather than just any solution. For example, dynamic programming can be used to find the shortest path between two nodes in a graph, or the longest common subsequence between two strings.

Many problems that are NP-hard can be solved in polynomial time using dynamic programming. This is because dynamic programming reduces the time complexity of a problem by breaking it down into smaller subproblems, and reusing the solutions to these subproblems instead of recomputing them each time they are needed.

What is the difference between a Dynamic programming technic and recursion?

Dynamic programming and recursion are two different techniques used to solve problems. The main difference between them is the way they approach a problem and store the solutions to subproblems. Dynamic programming stores the solutions to subproblems in a table, so they can be reused instead of recomputing them each time they are needed. This greatly reduces the time complexity of a problem, making it more efficient to solve. Recursion, on the other hand, breaks down a problem into smaller subproblems and solves them recursively, without storing the solutions. This can lead to a lot of duplicate work, and can make a problem very slow to solve, but it's often simpler to implement. Both methods have their own advantages and disadvantages and a problem can be solved using both methods, the choice of which method to use depends on the specific problem and the desired trade-off between time complexity and ease of implementation.

How to Identify if it is a Dynamic programming problem?

There are several ways to identify if a problem is a dynamic programming problem. One way is to look for overlapping subproblems, which occur when the same subproblem is solved multiple times with different inputs. Another way is to look for a problem that can be broken down into smaller subproblems, where the solution to the original problem can be constructed from the solutions to the subproblems.

Techniques to solve Dynamic Programming Problems.

There are several techniques that can be used to solve dynamic programming problems, including memoization, tabulation, and the use of recurrence relations. These techniques involve storing the solutions to subproblems in a table and reusing them instead of computing them each time they are needed. I will write more details about these technic next time. stay connected.

Let's take the example of Fibonacci series. The Fibonacci series is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence goes 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on.

// Fibonacci series using Dynamic programming (python code)
def fib(n, lookup):
  if n <= 0:
    lookup[n] = 0
    return 0
  if n == 1:
    lookup[n] = 1
    return 1
  if lookup[n] == None:
    lookup[n] = fib(n-1, lookup) + fib(n-2, lookup)
    return lookup[n]
n = 70
lookup = [None]*(101)
print("Fibonacci Number is : " , fib(n, lookup))

In this example, we are using the technique of memoization to store the solutions to subproblems in a table, and reusing them instead of recomputing them each time they are needed. This greatly reduces the time complexity of the problem, making it much more efficient to solve. Your computer will can't calculate the Fibonacci number of 70 with commonly used techniques. This is the power of dynamic programming.

In conclusion, dynamic programming is a powerful method of solving problems that can greatly reduce the time and space complexity of a problem. By breaking a problem down into smaller, overlapping subproblems, and storing the solutions to these subproblems in a table, we can greatly improve the efficiency of our algorithms. Feel free to reachout me to discus about problem solving.