सी # का उपयोग करके टॉपडाउन दृष्टिकोण का उपयोग करके न्यूनतम चरण को कैसे कार्यान्वित करें?

न्यूनतम StepstoOneTopdownApproach इनपुट के रूप में पूर्णांक n और एक पूर्णांक सरणी लेता है। पैरामीटर n में तत्वों की कुल संख्या होती है। प्रारंभिक स्थिति जांचती है कि n 1 के बराबर है या नहीं। यदि n 1 के बराबर है तो 0 पर लौटें। op1,op2 और op3 को अधिकतम मान पर प्रारंभ करें। यदि n mod 3 0 के बराबर है, तो MinimStepstoOneTopdownApproach को पुनरावर्ती कॉल करें और इसे op1 को असाइन करें, यदि n mod 3 0 के बराबर है, तो MinimStepstoOneTopdownApproach को पुनरावर्ती रूप से कॉल करें और इसे op2 को असाइन करें और n को 1 से घटाएं और न्यूनतमStepstoOneTopdownApproach पर कॉल करें। अंत में तीन तत्वों की न्यूनतम गणना करने के लिए Math.Min को कॉल करें और dp सरणी से मान वापस करें

समय की जटिलता - ओ(एन)

अंतरिक्ष जटिलता - ओ(एन)

उदाहरण

public class DynamicProgramming{
   public int MinimumStepstoOneTopdownApproach(int n, int[] dp){
      if (n == 1){
         return 0;
      }
      int op1, op2, op3;
      op1 = int.MaxValue; op2 = int.MaxValue; op3 = int.MaxValue;
      if (n % 3 == 0){
         op1 = MinimumStepstoOneTopdownApproach(n / 3, dp);
      }
      if (n % 2 == 0){
         op2 = MinimumStepstoOneTopdownApproach(n / 2, dp);
      }
      op3 = MinimumStepstoOneTopdownApproach(n -1, dp);
      int ans = Math.Min(Math.Min(op1, op2), op3)+1;
      return dp[n] = ans;
   }
}

static void Main(string[] args){
   DynamicProgramming dp = new DynamicProgramming();
   int[] dpArr = new int[150];
   Console.WriteLine(dp.MinimumStepstoOneTopdownApproach(10, dpArr));
}

आउटपुट

3