CoinChangeBottomUpApproach 3 প্যারামিটার নেয় কারণ ইনপুট n হল পরিমাণ, কয়েন অ্যারেতে কয়েনের মোট সংখ্যা থাকে, 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
