CoinChangeTopDownApproach चार पैरामीटर लेता है: n राशि है, coins ऐरे में वे सिक्के होते हैं जिनसे राशि की गणना की जानी है, t सिक्कों की कुल संख्या है, dp ऐरे सभी पूर्व-गणना किए गए मानों को संग्रहीत करेगा। यदि राशि 0 है तो 0 लौटाएं। यदि मान पहले से गणना किया गया है तो dp ऐरे से लौटाएं। यदि मान गणना नहीं किया गया है तो CoinChangeTopDownApproach को पुनरावर्ती रूप से कॉल करें।
समय जटिलता − O(N)
स्पेस जटिलता − O(N)
उदाहरण
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
