最適なアルゴリズム

Question

私は入力 "N"を与えられました。追加される次の数が追加された最大数より1つ多くなるように、長さNのリストの番号を1から始める必要があります今まで。 （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

この問題は、ダイナミックプログラミングの問題の典型的な例である：

あなたが最大数Mであるため、長さkのリストの数であることが関数DP（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の唯一のリストがあり、その最大の要素は、あなたが最大の要素mの長さkのリストを構築しているときは、のいずれかを取ることができます。1. です（k-1） - max = mおよび1または2または...またはmの付いたリスト。または、最大要素m-1でmを追加して（k-1）リストを取ることができます。最大要素がm-1より小さい（k-1）リストを取るならば、あなたの規則では、ただ1つの要素を追加することによって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)です。

---

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); 

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; 
    } 

他とかなり似ています。私はこの "古典的な動的プログラミング"を単に "古典的な再帰"と呼ぶことはありません。