CoinChangeBottomUpApproach는 3개의 매개변수를 취합니다. 입력 n은 금액이고, coin 배열은 총 동전 수를 포함하고, t는 총 동전 수를 포함합니다. 이전에 계산된 값을 저장하는 동적 배열을 선언합니다. 배열을 반복하고 금액을 계산하는 데 필요한 최소 동전을 계산합니다. 계산이 이미 완료된 경우 동적 배열에서 값을 가져옵니다.
시간 복잡도 − 오(N)
공간 복잡성 − 오(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