CoinChangeTopDownApproach 4 প্যারামিটার নেয়, n হল পরিমাণ, কয়েন অ্যারেতে কয়েন থাকে যেখান থেকে পরিমাণ গণনা করা প্রয়োজন, 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
