数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究如何使用自底向上的方法用 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
更新于： 17-8-2021
438 次浏览
广告