How to solve dynamic problem using recursion easily

When ever a dynamic problem comes we start thinking a lot. After reading the problem we think for each possible situation and at last, we come to the conclusion that we have to go through many possible ways. Apart from that, implementing the solution may require many loops to check each possible case. But we have a lethal weapon called recursion.

What is recursion?

Recursion is a function calling itself. To solve problems we need to think of the breakpoints in it and call the function again. After that, the function does all the job by itself and returns the value whenever it reaches the breakpoint. It automatically covers all the possible cases. And to write a recursion function, we have to replicate what we are thinking.

We will try to solve one of the most famous questions Longest Common Subsequence (LCS).

So what is the Longest Common Subsequence problem?

Two strings will be provided to us and we have to find the length of the longest common subsequence present in both of them. A subsequence is basically a sequence of characters occurring in the same relative order. For ex — A string “abcd” can have subsequence like “acd”, “adb” etc.

Sample input -

String A — “acbaed”

String B — “abcadf”

Sample output -

Length — 4 (“acad” or “abad”)

Now take a pause and think for the solution… ✋🏻

Let’s try to think for the solution

So what can be the breakpoints for this problem? We will try to traverse both the strings from backward.

Now its coding time which is easier

We will just try to replicate our breakpoints here

That’ s it we just solved one of the most complex problems in just a few lines.

Try to find the length of Longest Palindromic Subsequence

What is the Longest Palindromic Subsequence problem?

A string will be given, we have to find a subsequence in the string which is same from forward and backward. Since it is a subsequence, the characters should not be contiguous. For ex — if the input string is “ABBDCACB”, the answer will be 5 because the string will be “BCACB”.

Hint — We have to use the Longest Common Subsequence algorithm, just have to decide what will be the input.

We just have learned that every dynamic problem can be solved using recursion function easily. For that, we just have to think of the possibilities and breakpoint for that problem and replicate it in our code.

Hope this article was helpful for you. If you liked, a few claps 👏🏻 and shares will be appreciated. And if you want to know whether your solution for Longest Common Subsequence is right? or you want to know the solution let me know in the response.

Related posts:

I have a goal. It is simple. It’s one I’ve lived my whole life by — or at least try to. It’s one my friends and exes have constantly remarked on with some amount astonishment or approval. I don’t…