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
