1

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

N = 3, possible lists => (111, 112, 121, 122, 123), [113, or 131 是不可能的，因此我们只能添加 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：我只想知道此类列表的数量，因此我确信不需要创建所有列表。（我在代码中的做法）我在算法方面一点也不擅长，所以请原谅这个冗长的问题。

4

2 回答 2

3

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

如果您将函数 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 的列表时，您可以获取任何 (k-1) 列表，其中 max = m 并附加1 或 2 或 .... 或 m。或者你可以使用一个最大元素为 m-1 的 (k-1)-list 并附加 m。如果您采用最大元素小于 m-1 的 (k-1)-list，那么根据您的规则，您不能通过仅附加一个元素来获得最大 m。

您可以使用动态编程计算所有 k = 1,...,N 和 m = 1,...,N+1 的 dp(k,m) ，O(N^2)然后您的问题的答案是

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

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

C#中dp计算的实现见下文：

        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);
于 2012-04-07T19:56:59.697 回答
0

好吧，今天下午我被一场大火打断了（真的！）但是 FWIW，这是我的贡献：

    /*
     * Counts the number of possible integer list on langth N, with the
     * property that no integer in a list(starting with one) may be more
     * than one greater than the greatest integer preceeding it in the list.
     * 
     * I am calling this "Semi-Factorial" since it  is somewhat similar to
     * the factorial function and its constituent integer combinations.
     */
    public int SemiFactorial(int N)
    {
        int sumCounts = 0;

        // get a list of the counts of all valid lists of length N,
        //whose maximum integer is listCounts[maxInt].
        List<int> listCounts = SemiFactorialCounts(N);

        for (int maxInt = 1; maxInt <= N; maxInt++)
        {
            // Get the number of lists, of length N-1 whose maximum integer
            //is (maxInt):
            int maxIntCnt = listCounts[maxInt];

            // just sum them up
            sumCounts += maxIntCnt;
        }

        return sumCounts;
    }

    // Returns a list of the counts of all valid lists of length N, and
    //whose maximum integer is [i], where [i] is also its index in this
    //returned list. (0 is not used).
    public List<int> SemiFactorialCounts(int N)
    {
        List<int> cnts;
        if (N == 0)
        {
            // no valid lists, 
            cnts = new List<int>();
            // (zero isn't used)
            cnts.Add(0);
        }
        else if (N == 1)
            {
                // the only valid list is {1}, 
                cnts = new List<int>();
                // (zero isn't used)
                cnts.Add(0);
                //so that's one list of length 1
                cnts.Add(1);
            }
            else
            {
            // start with the maxInt counts of lists whose length is N-1:
            cnts = SemiFactorialCounts(N - 1);

            // add an entry for (N)
            cnts.Add(0);

            // (reverse order because we overwrite the list using values
            // from the next lower index.)
            for (int K = N; K > 0; K--) 
            {
                // The number of lists of length N and maxInt K { SF(N,K) }
                // Equals K times # of lists one shorter, but same maxInt,
                // Plus, the number of lists one shorter with maxInt-1.
                cnts[K] = K * cnts[K] + cnts[K - 1];
            }
        }

        return cnts;
    }

与其他人非常相似。尽管我不会将其称为“经典动态编程”，而只是称为“经典递归”。

于 2012-04-07T21:26:34.350 回答