## Ways to Solve Dynamic Programming Problems

There are two different ways to store the values so that the values of a sub-problem can be reused. Both are discussed below :

**Tabulation or Bottom-up:** Bottom-up is a technique that saves memory by avoiding Recursion, which has been incurred by recursion call stack. Bottom-up means starting from the beginning.
**Memoisation or Top-down: **Memoisation assures that a function doesn't run again for the same inputs again and again by keeping a record of the results for the previously given inputs.

Let's look at an example to clearly understand the concept:

**Fibonacci Number Series:**

**Recursive approach**

```
int fibonacci(int n) {
if (n <= 1)
return n;
int a = fibonacci(n - 1);
int b = fibonacci(n - 2);
return a + b;
}
```

**Time-complexity : 2^n**

**Memoisation approach**

```
int fib_helper(int n, int * ans) {
if (n <= 1)
Return n;
if (ans[n] != -1)
Return ans[n];
Int a = fib_helper(n - 1, ans);
Int b = fib_helper(n - 2, ans);
Return ans[n] = a + b;
}
int fib(int n) {
int * ans = new int[n + 1];
for (int i = 0; i <= n; i++) {
ans[i] = -1;
}
return fib_helper(n, ans);
}
```

**Time-complexity : O(n)**

**Bottom-up approach**

```
int fibo(int n) {
int * ans = new int[n + 1];
ans[0] = 1;
ans[1] = 1;
for (int i = 2; i <= n; i++) {
ans[i] = ans[i - 1] + ans[i - 2];
}
return ans[n];
}
```

**Time-complexity : O(n)**

In depth discussion of the difference between tabulation is memoization is given __here__

Check out__ Longest Common Substring__

## Variations of Dynamic Programming Problems

There isn't any set of variations of problems in which a DP problem lies but frequently asked problems have a certain set of variations we will be discussing below:

**Stock Variation**

In this type of problem variation, we are generally asked to calculate the maximum profit one can make from the given daily trading chart by setting the number of times one can buy or sell the stock. Now ,clearly it is asking for an optimised result and we are given with choices to pick the stock to buy or sell, therefore it is a variation of dynamic programming problem. Refer to __this__ for more details.

**Expression Matching**

In this type of problem variation, we are asked to match two strings by setting some wildcard rules for some characters. Here, we have the choice to choose from which index we use this wildcard. Therefore it is a Dynamic programming problem. Refer to __this__ for more details.

**LCS and its variations**

In this variation type, we are given two strings and maybe asked to calculate the longest common substring or maybe given one string and asked to calculate the longest palindromic substring. Here ,we are asked for an optimised result and are given with choices whether to pick the element or not in the final result. Therefore, it is a variation of dynamic programming problem. Refer to __this__ for more details.

**0-1 Knapsack and its variations**

In 0-1 knapsack problem and its variations, we are given with an array and asked to get the maximum profit while picking elements from the array by setting constrain on either the money or weight or any such entity. Since, we are asked to get an optimised result by picking or not picking elements from the array. Therefore it is a dynamic programming problem. Refer to __this__** **for more details.

Must Read __Julia Programming Language__

## Frequently Asked Questions

**What is Dynamic Programming?**

A dynamic problem is an algorithm for solving bigger problems by dividing them into smaller subproblems, keeping in mind that the optimal solution to bigger problems lies in smaller subproblems.

**How is Dynamic Programming different from normal programming?**

Dynamic programming is not "programming" in that sense. It is not about writing code, but the word "programming" there is used in the context of solving complex problems by breaking them down into simpler problems.

**How to solve a Dynamic Programming problem?**

The first step is to identify the problem. The next step is to identify what type of variation it is, if possible. By doing so, it would be easy to solve the problem.

## Conclusion

In this article, we have discussed dynamic programming, what kind of problems can be solved by dynamic programming, the difference between DP and Recursion, and finally, variations of problems in Dynamic Programming.

Refer to our __guided paths on Coding Ninjas Studio__ to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our __courses__ and refer to the __mock test__ and __problems__ available, __interview puzzles__, take a look at the __interview experiences__, and __interview bundle__ for placement preparations.

We hope that this blog has helped you enhance your knowledge regarding puzzles, and if you liked this blog, check other links.

Do upvote our blog to help other ninjas grow.

Happy Coding!"