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

CoinChangeBottomUpApproach 3 पैरामीटर लेता है क्योंकि इनपुट n राशि है, सिक्कों की सरणी में सिक्कों की कुल संख्या होती है, t में सिक्कों की कुल संख्या होती है। एक गतिशील सरणी घोषित करें जो पहले परिकलित मानों को संग्रहीत करता है। सरणी के माध्यम से लूप करें और राशि की गणना करने के लिए आवश्यक न्यूनतम सिक्कों की गणना करें। यदि गणना पहले ही की जा चुकी है, तो गतिशील सरणी से मान लें।

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

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

उदाहरण

public class DynamicProgramming{
   public int CoinChangeBottomUpApproach(int n,int[] coins,int t){
      int[] dp = new int[100];
      for (int i = 1; i < n; i++){
         dp[i] = int.MaxValue;
         for (int j = 0; j < t; j++){
            if (i - coins[j] >= 0){
               int subProb = dp[i - coins[j]];
               dp[i] = Math.Min(dp[i], subProb + 1);
            }
         }
      }
      return dp[n]+1;
   }
}

static void Main(string[] args){
   DynamicProgramming dp = new DynamicProgramming();
   int[] coins = { 1, 7, 10 };
   int ss = dp.CoinChangeBottomUpApproach(15, coins, coins.Count());
   Console.WriteLine(ss);
}

आउटपुट

3