algorithm - 最优算法

Question

我有一个输入，“N”，我必须找到长度为 N 的列表的数量，它以 1 开头，这样下一个要添加的数字最多比到目前为止添加的最大数量多 1 .例如，

N = 3, possible lists => (111, 112, 121, 122, 123), [113, or 131 is not possible as while adding '3' to the list, the maximum number present in the list would be '1'，因此我们只能添加 1 或 2]。

N = 4，列表1213是可能的，因为在添加3时，列表中的最大数量是'2'，因此可以添加3。

问题是计算给定输入“N”可能出现的此类列表的数量。

我的代码是:-

public static void Main(string[] args)
        {
            var noOfTestCases = Convert.ToInt32(Console.ReadLine());
            var listOfOutput = new List<long>();
            for (int i = 0; i < noOfTestCases; i++)
            {
                var requiredSize = Convert.ToInt64(Console.ReadLine());
                long result;
                const long listCount = 1;
                const long listMaxTillNow = 1;
                if (requiredSize < 3)
                    result = requiredSize;
                else
                {
                    SeqCount.Add(requiredSize, 0);
                    AddElementToList(requiredSize, listCount, listMaxTillNow);
                    result = SeqCount[requiredSize];
                }
                listOfOutput.Add(result);
            }
            foreach (var i in listOfOutput)
            {
                Console.WriteLine(i);
            }
        }

        private static Dictionary<long, long> SeqCount = new Dictionary<long, long>();

        private static void AddElementToList(long requiredSize, long listCount, long listMaxTillNow)
        {
            if (listCount == requiredSize)
            {
                SeqCount[requiredSize] = SeqCount[requiredSize] + 1;
                return;
            }
            var listMaxTillNowNew = listMaxTillNow + 1;
            for(var i = listMaxTillNowNew; i > 0; i--)
            {
                AddElementToList(requiredSize, listCount + 1,
                    i == listMaxTillNowNew ? listMaxTillNowNew : listMaxTillNow);
            }
            return;
        }

这是蛮力法。我想知道解决该问题的最佳算法是什么？PS:我只想知道此类列表的数量，因此我确信不需要创建所有列表。 (我在代码中做的方式)我一点也不擅长算法，所以请原谅这个长问题。

Answer 1

这个问题是动态规划问题的经典例子:

如果你定义一个函数 dp(k, m) 为长度为 k 的列表的数量，其中最大数量为 m，那么你有一个递归关系:

dp(1, 1) = 1
dp(1, m) = 0, for m > 1
dp(k, m) = dp(k-1, m) * m + dp(k-1, m-1)

确实，只有一个长度为1的列表，其最大元素为1。当您构建一个长度为 k 且最大元素为 m 的列表时，您可以采用任何具有 max = m 的 (k-1)-列表并附加 1 或 2 或 .... 或 m。或者您可以使用最大元素为 m-1 的 (k-1)-list 并附加 m。如果您采用最大元素小于 m-1 的 (k-1)-list，那么根据您的规则，您无法通过仅附加一个元素来获得 m 的最大值。

您可以使用 O(N^2) 中的动态规划为所有 k = 1,...,N 和 m = 1,...,N+1 计算 dp(k,m)那么你的问题的答案就是

dp(N,1) + dp(N,2) + ... + dp(N,N+1)

因此算法是O(N^2) .

---

dp计算在C#中的实现见下:

        int[] arr = new int[N + 2];
        for (int m = 1; m < N + 2; m++)
            arr[m] = 0;
        arr[1] = 1;

        int[] newArr = new int[N + 2];
        int[] tmp;
        for (int k = 1; k < N; k++)
        {
            for (int m = 1; m < N + 2; m++)
                newArr[m] = arr[m] * m + arr[m - 1];
            tmp = arr;
            arr = newArr;
            newArr = tmp;
        }

        int answer = 0;strong text
        for (int m = 1; m < N + 2; m++)
            answer += arr[m];

        Console.WriteLine("The answer for " + N + " is " + answer);