Оптимальный алгоритм

Question

Мне дан ввод «N», мне нужно найти номер списка длины N, который начинается с 1, так что следующее добавленное число не более 1 больше, чем максимальное число добавлено до настоящего времени. Например,

N = 3, возможные списки => (111, 112, 121, 122, 123), [113 или 131 невозможно, так как при добавлении «3» в список максимальное число, присутствующее в списке список будет «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(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-1) -листов с max = m и добавьте 1 или 2 или .... или m. Или вы можете взять (k-1) -list с максимальным элементом m-1 и добавить m. Если вы берете (k-1) -list с максимальным элементом меньше m-1, то по вашему правилу вы не можете получить максимум m, добавив только один элемент.

Вы можете вычислить dp (k, m) для всех k = 1, ..., N и m = 1, ..., N + 1, используя динамическое программирование в O(N^2), а затем ответ на ваш вопрос будет

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

Таким образом, алгоритм O(N^2).

---

Ниже для осуществления расчета йра в 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); 

Answer 2

Ну, я был прерван огнем во второй половине дня (на самом деле!), Но 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; 
    } 

довольно похоже на другие. Хотя я бы не назвал это «классическое динамическое программирование» так же, как просто «классическая рекурсия».