เมธอด CoinChangeTopDownApproach รับพารามิเตอร์ 4 ตัว: n คือจำนวนเงินเป้าหมาย coins คืออาร์เรย์เหรียญ t คือจำนวนชนิดเหรียญ dp คืออาร์เรย์เก็บค่าที่คำนวณไว้ หาก n เท่ากับ 0 คืนค่า 0 หากคำนวณแล้ว คืนค่าจาก dp หากยังไม่ได้คำนวณ เรียกเมธอดซ้ำ (Recursive)
Time Complexity: O(N)
Space Complexity: 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.Length;
int res = dp.CoinChangeTopDownApproach(15, coins, t, dp1);
Console.WriteLine(res);
}ผลลัพธ์
3
