What do you understand about the Dynamic Programming (DP) Algorithmic

1.	What do you understand about the Dynamic Programming (DP) Algorithmic Paradigm? List a few problems which can be solved using the same.
Answer» Dynamic Programming is primarily a RECURSION optimization. We can use Dynamic Programming to optimise any recursive solution that involves repeated calls for the same inputs. The goal is to simply save the results of subproblems so that we do not have to recalculate them later. The time complexity of this simple optimization is reduced from exponential to polynomial. For example, if we create a simple recursive solution for Fibonacci Numbers, the time complexity is exponential, but if we optimise it by storing subproblem answers using Dynamic Programming, the time complexity is linear. The following codes illustrate the same: With Recursion (no DP): The time complexity of the given code will be exponential. /Sample C++ code for finding nth fibonacci number without DP/int nFibonacci(int n){ if(n == 0 \|\| n == 1) return n; else return nFibonacci(n - 1) + nFibonacci(n - 2);} With DP: The time complexity of the given code will be linear because of Dynamic Programming. /Sample C++ code for finding nth fibonacci number with DP/int nFibonacci(int n){ vector<int> fib(n + 1); fib[0] = 0; fib[1] = 1; for(int i = 2;i <= n;i ++){ fib[i] = fib[i - 1] + fib[i - 2]; } return fib[n]; } A few problems which can be solved using the Dynamic Programming (DP) Algorithmic Paradigm are as follows: Finding the nth Fibonacci number Finding the Longest Common Subsequence between two strings. Finding the Longest Palindromic SUBSTRING in a string. The discrete (or 0-1) Knapsack Problem. Shortest Path between any two nodes in a graph (FLOYD Warshall Algorithm)

What do you understand about the Dynamic Programming (DP) Algorithmic Paradigm? List a few problems which can be solved using the same.

Answer»

Dynamic Programming is primarily a RECURSION optimization. We can use Dynamic Programming to optimise any recursive solution that involves repeated calls for the same inputs. The goal is to simply save the results of subproblems so that we do not have to recalculate them later. The time complexity of this simple optimization is reduced from exponential to polynomial. For example, if we create a simple recursive solution for Fibonacci Numbers, the time complexity is exponential, but if we optimise it by storing subproblem answers using Dynamic Programming, the time complexity is linear.

The following codes illustrate the same:

With Recursion (no DP): The time complexity of the given code will be exponential.

/*Sample C++ code for finding nth fibonacci number without DP*/int nFibonacci(int n){ if(n == 0 || n == 1) return n; else return nFibonacci(n - 1) + nFibonacci(n - 2);}

With DP: The time complexity of the given code will be linear because of Dynamic Programming.

/*Sample C++ code for finding nth fibonacci number with DP*/int nFibonacci(int n){ vector<int> fib(n + 1); fib[0] = 0; fib[1] = 1; for(int i = 2;i <= n;i ++){ fib[i] = fib[i - 1] + fib[i - 2]; } return fib[n]; }

A few problems which can be solved using the Dynamic Programming (DP) Algorithmic Paradigm are as follows:

Finding the nth Fibonacci number
Finding the Longest Common Subsequence between two strings.
Finding the Longest Palindromic SUBSTRING in a string.
The discrete (or 0-1) Knapsack Problem.
Shortest Path between any two nodes in a graph (FLOYD Warshall Algorithm)

What do you understand about the Dynamic Programming (DP) Algorithmic Paradigm? List a few problems which can be solved using the same.

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment