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

CoinChangeTopDownApproach 4 पैरामीटर लेता है, n राशि है, सिक्के सरणी में वे सिक्के हैं जिनसे राशि की गणना की जानी है, t सिक्कों की कुल संख्या है, dp सरणी सभी पूर्व परिकलित मान। यदि राशि 0 है तो 0 लौटाएं। यदि मान पहले से ही गणना की गई है तो डीपी सरणी से वापस आएं। यदि मान की गणना नहीं की जाती है तो CoinChangeTopDownApproach को पुनरावर्ती रूप से कॉल करें।

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

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

उदाहरण

public class DynamicProgramming{
   public int CoinChangeTopDownApproach(int n,int[] coins,int t,int[] dp){
      if (n == 0){
         return 0;
      }
      if (dp[n] != 0){
         return dp[n];
      }
      int ans = int.MaxValue;
      for (int i = 0; i < t; i++){
         if (n - coins[i] >= 0){
            int subprob = CoinChangeTopDownApproach(n - coins[i], coins, t, dp);
            ans = Math.Min(ans, subprob + 1);
      }
   }
   dp[n] = ans;
   return dp[n];
   }
}

static void Main(string[] args){
   DynamicProgramming dp = new DynamicProgramming();
   int N = 15;
   int[] coins = { 1, 7, 10 };
   int[] dp1 = new int[100];
   int t = coins.Count();
   int res = dp.CoinChangeTopDownApproach(15, coins, t, dp1);
   Console.WriteLine(res);
}

आउटपुट

3