Recursion Archives - SimpleTechTalks

Print longest common subsequence string of two string

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…)

Longest common subsequence problem using dynamic programming

by admin

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.

(more…)

Finding number of ways to write “n” as sum of multiple smaller numbers

by Sandeep Kumar

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.

(more…)

Dynamic Programming approach explained with simple example

by Sandeep Kumar

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.

(more…)