计算不同子序列的时间复杂度

Question

问题来自leetcode，我想出了下面的代码，但我很难找到它的时间复杂性。知道如何计算它的时间复杂度吗？(如果没有字典记忆呢)

        public int NumDistinct (string s, string t)
        {
            if (string.IsNullOrEmpty (s) && string.IsNullOrEmpty (t))
                return 1;
            else if (string.IsNullOrEmpty (s) || string.IsNullOrEmpty (t))
                return 0;

            return FindSequences (s, 0, t, 0);
        }

        Dictionary<string, int> memoery = new Dictionary<string, int> ();

        private int FindSequences (string s, int idxs, string t, int idxt)
        {
            if (idxt == t.Length)
                return 1;
            else if (idxs == s.Length)
                return 0;

            string key = string.Format ("{0}-{1}", idxs, idxt);
            if (memoery.ContainsKey (key))
                return memoery [key];

            int result = 0;
            if (s [idxs] == t [idxt]) {
                result = FindSequences (s, idxs + 1, t, idxt + 1) + FindSequences (s, idxs + 1, t, idxt);
            } else {
                result = FindSequences (s, idxs + 1, t, idxt);
            }
            memoery.Add (key, result);
            return result;
        }

Answer 1

这里的时间复杂性是O(SizeOf(s) * SizeOf(t))。对于Dynamic Programming Solutions，您可以使用不同状态的数量来计算时间复杂度，这里的状态量是SizeOf(s) * sizeOf(t)。

动态规划使用了Memoisation的概念，即存储状态的结果，这样当我们遇到相同的状态时，就可以使用它，因此我们有效地不进行冗余计算，因为状态经常重复，而当它们重复时，我们使用之前计算的结果来降低时间复杂度。

还请注意，时间复杂性还取决于Look up table或DP Table，在上述情况下，这是一个Dictionary，因此您还必须考虑Dictionary Look up和Dictionary Insertion的时间，从而有效地使复杂性达到：

O(SizeOf(s) * SizeOf(t) * Time to look Up or insert in Dictionary)。