如何使用 C# 使用自下而上的方法实现硬币找零问题?
CoinChangeBottomUpApproach接受3个参数作为输入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