Memoization

Memoization is a technique used in dynamic programming to optimize recursive solutions by storing previously computed results and reusing them instead of recomputing the same values multiple times. By storing the results in a memoization table or cache, we can avoid redundant calculations and improve the overall runtime of the algorithm.

In the context of the Longest Common Subsequence problem, memoization can be used to optimize the recursive solution. As we discussed earlier, the recursive solution has overlapping subproblems, which leads to redundant calculations. By using memoization, we can store the results of subproblems in a table and look them up whenever needed.

Here's an example of how the memoization technique can be implemented in C#:

1using System;
2
3class Program
4{
5    static int[, ] memo;
6
7    static int LongestCommonSubsequence(string s1, string s2, int m, int n)
8    {
9        if (m == 0 || n == 0)
10        {
11            return 0;
12        }
13
14        if (memo[m, n] != -1)
15        {
16            return memo[m, n];
17        }
18
19        if (s1[m - 1] == s2[n - 1])
20        {
21            memo[m, n] = 1 + LongestCommonSubsequence(s1, s2, m - 1, n - 1);
22        }
23        else
24        {
25            memo[m, n] = Math.Max(LongestCommonSubsequence(s1, s2, m - 1, n), LongestCommonSubsequence(s1, s2, m, n - 1));
26        }
27
28        return memo[m, n];
29    }
30
31    static void Main(string[] args)
32    {
33        string s1 = "algorithm";
34        string s2 = "program";
35
36        int m = s1.Length;
37        int n = s2.Length;
38
39        memo = new int[m + 1, n + 1];
40        for (int i = 0; i <= m; i++)
41        {
42            for (int j = 0; j <= n; j++)
43            {
44                memo[i, j] = -1;
45            }
46        }
47
48        int length = LongestCommonSubsequence(s1, s2, m, n);
49        Console.WriteLine("Length of the Longest Common Subsequence: " + length);
50    }
51}

In the above example, we define a memoization table memo to store the results of subproblems. Before making any recursive calls, we check if the result for the current subproblem already exists in the memoization table. If it does, we return the stored result. Otherwise, we compute the result and store it in the table for future use.

By using this memoization technique, we can significantly reduce the number of recursive calls and avoid redundant calculations. This leads to improved runtime and a more efficient solution.

It's important to note that memoization works well for problems with overlapping subproblems, like the Longest Common Subsequence problem. However, it may not be as effective for problems with non-overlapping subproblems.

The memoization technique is a powerful optimization technique in dynamic programming and is widely used to improve the efficiency of recursive solutions. By avoiding repeated calculations, we can solve complex problems more efficiently and optimize the overall runtime of the algorithm.

xxxxxxxxxx

}

using System;

​

class Program

{

    static int[, ] memo;

​

    static int LongestCommonSubsequence(string s1, string s2, int m, int n)

    {

        if (m == 0 || n == 0)

        {

            return 0;

        }

​

        if (memo[m, n] != -1)

        {

            return memo[m, n];

        }

​

        if (s1[m - 1] == s2[n - 1])

        {

            memo[m, n] = 1 + LongestCommonSubsequence(s1, s2, m - 1, n - 1);

        }

        else

        {

            memo[m, n] = Math.Max(LongestCommonSubsequence(s1, s2, m - 1, n), LongestCommonSubsequence(s1, s2, m, n - 1));

        }

​

        return memo[m, n];

    }