資料結構
網路
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 次瀏覽
廣告