資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時裝研究
法律研究如何使用 C# 中的 topDown 方法實現找零問題？
CoinChangeTopDownApproach 接收 4 個引數，n 是金額，coins 陣列包含需要計算金額的硬幣，t 是硬幣總數，dp 陣列將儲存所有預先計算的值。如果金額為 0，則返回 0。如果已經計算出該值，則從 dp 陣列中返回。如果尚未計算出該值，則透過遞迴呼叫 CoinChangeTopDownApproach。
時間複雜度 − O(N)
空間複雜度 − O(N)
示例
public class DynamicProgramming{
public int CoinChangeTopDownApproach(int n,int[] coins,int t,int[] dp){
if (n == 0){
return 0;
}
if (dp[n] != 0){
return dp[n];
}
int ans = int.MaxValue;
for (int i = 0; i < t; i++){
if (n - coins[i] >= 0){
int subprob = CoinChangeTopDownApproach(n - coins[i], coins, t, dp);
ans = Math.Min(ans, subprob + 1);
}
}
dp[n] = ans;
return dp[n];
}
}
static void Main(string[] args){
DynamicProgramming dp = new DynamicProgramming();
int N = 15;
int[] coins = { 1, 7, 10 };
int[] dp1 = new int[100];
int t = coins.Count();
int res = dp.CoinChangeTopDownApproach(15, coins, t, dp1);
Console.WriteLine(res);
}輸出
3
更新時間： 2021 年 8 月 17 日
瀏覽量 1K+
廣告