최적 알고리즘

Question

입력이 "N"인 경우 길이가 N 인 목록의 번호를 찾아야 만합니다. 추가 할 다음 번호가 추가 된 최대 숫자보다 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; 
     } 

. 문제의 가장 좋은 알고리즘이 무엇인지 알고 싶습니다. 추신 : 나는 그러한 목록의 수를 알고 싶습니다. 그래서 모든 목록을 만들 필요는 없습니다. (코드에서 내가하는 방법) 알고리즘에 전혀 좋지 않으므로 긴 질문에 대해 변명하십시오.

Answer 1

이 문제는 동적 프로그래밍 문제의 고전적인 예이다 :

당신에게 다음으로, 최대 수 m되는 길이 k의리스트의 번호로 기능 DP (K, m)를 정의하면 이 길이가 1 인 하나의 목록이며, 최대 요소는 1. 당신이 최대 요소 m에 길이 k의 목록을 작성하는 경우, 당신이 중 하나를 취할 수있다, 실제로

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

: 재발의 관계가 (k-1) - max = m 및 1 또는 2 또는 .... 또는 m을 갖는리스트. 또는 (k-1) - 최대 원소가 m-1 인리스트를 취해 m을 붙일 수 있습니다. max-element가 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)입니다. (! 정말)

 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, 여기 내 공헌의 :

---

C#에서 DP 계산의 구현은 아래를 참조하십시오

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

다른 사람들과 매우 유사합니다. 비록이 "고전적인 동적 프로그래밍"을 단순히 "고전적인 재귀"라고 부르지는 않겠지 만.