プログラミングコンテストチャレンジブック p56 最長共通部分列問題(C#)

問題

二つの文字列sとtが与えられる。これら２つの共通部分文字列の長さの最大値を求めなさい。ただし、文字列s1,s2,s3,...の部分文字列とは、si1,si2...sim(i1 < i2 < im)を表すことのできる文字列のことを言います。

自分(正解)

全探索で解いて、出力があっていた。しかし、この章で学習する内容は、「動的計画法」なので、その点では間違えているとも言える。

using System;

public class Program
{
    public static void Main()
    {
        int n = 4;
        int m = 4;
        int ans;

        string s = "abcd";
        string t = "becd";
        char[] s_arr = s.ToCharArray();
        char[] t_arr = t.ToCharArray();

        ans = Math.Max(exec(s_arr, t_arr), exec(t_arr, s_arr));

        Console.WriteLine("候補1：{0}",exec(s_arr, t_arr));
        Console.WriteLine("候補2：{0}",exec(t_arr, s_arr));
        Console.WriteLine("答え：{0}",ans);


        int exec(char[] arr1, char[] arr2)
        {
            int i = 0;
            foreach (char c in arr1)
            {
                int j = 0;
                foreach (char c2 in arr2)
                {
                    if (c == c2)
                    {
                        var l = i + 1;
                        var m = j + 1;

                        arr1 = arr1[l..];
                        arr2 = arr2[m..];
                        return exec(arr1, arr2) + 1;
                    }
                    j++;
                }
                i++;
            }
            return 0;
        }
    }
}

解答：動的計画法