To make technologies simpler
by The longest increasing sub sequence (LIS) is the problem in which we need to find out the length of the longest increasing sub sequence in the given sequence. In this case, numbers doesn’t require to be in consecutive places.
For eg:
The length of LIS in the sequence {1, 2, 2, 5, 8, 6, 3, 6, 9, 7} is 7 and the longest increasing sub sequence is {1, 2, 2, 5, 6, 6, 7}
by The longest subsequence problem (LCS) is the problem in which we need to find the longest subsequence present in two sequences. In this case, characters doesn’t require to be in consecutive places.
For eg:
LCS for sequence “ABCDFG” and “ABCGDFG” is “ABCDFG” and its length is 6.
For calculating longest common subsequence length we can use recursion or dynamic programming, here we are going to see how to find the longest common subsequence string.
(more…)by This problem can be solved using multiple approaches but here we will solve this problem using Dynamic Programming and showcase how dynamic programming will make the execution super-fast.
We will go through with the same steps as mentioned in Dynamic Programming post to tackle this problem step by step for better understanding.
Let’s explain the problem,
The longest subsequence problem (LCS) is the problem in which we need to find the longest subsequence present in two sequences. In this case, characters doesn’t require to be in consecutive places.
For eg:
LCS for sequence “ABCDFG” and “ABCGDFG” is “ABCDFG” and its length is 6.
Let’s apply the 3 Steps rule (Dynamic Programming) to tackle this problem.
by This problem can be solved using multiple approaches but here we will solve this problem using Dynamic Programming and showcase how dynamic programming will make the execution super-fast.
We will go through with the same steps as mentioned in Dynamic Programming post to tackle this problem step by step for better understanding.
Let’s explain the problem,
given n, find the number of different ways to write “n” as the sum of 1, 3, 4
Example:
for n = 5, the answer is 6
5 = 1+1+1+1+1
= 1+1+3
= 1+3+1
= 3+1+1
= 1+4
= 4+1
Let’s apply the 3 Steps rule to tackle this problem.
by Dynamic Programming is a programming technique which is used for solving complex problems by breaking it into comparatively simpler subproblems and finding the optimal solutions of the complex problems by finding the optimal solutions of these subproblems.
Even though, the name “Dynamic Programming” might scare people but actually its kind of simple if we follow some basic techniques to approach any complex problem.
Steps to tackle a problem using Dynamic Programming approach:
1) Define smaller problems from the original complex problems.
2) Solve these smaller problems using recursion.
3) Use smaller problems results to solve the bigger complex problem.