CoinChangeBottomUpApproach तीन पैरामीटर इनपुट के रूप में लेता है: n राशि है, coins ऐरे में सिक्कों की कुल संख्या होती है, t में सिक्कों की कुल संख्या होती है। एक डायनामिक ऐरे घोषित करें जो पहले से गणना किए गए मानों को संग्रहीत करता है। ऐरे के माध्यम से लूप करें और राशि की गणना के लिए आवश्यक न्यूनतम सिक्कों की गणना करें। यदि गणना पहले से की जा चुकी है तो डायनामिक ऐरे से मान लें।
समय जटिलता − O(N)
स्पेस जटिलता − O(N)
उदाहरण
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