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
