การแก้ปัญหา Coin Change ด้วยวิธี Bottom-Up ใน C#

เมธอด CoinChangeBottomUpApproach รับพารามิเตอร์ 3 ตัว: n คือจำนวนเงินเป้าหมาย coins คืออาร์เรย์ของเหรียญที่มีอยู่ t คือจำนวนชนิดของเหรียญ ใช้ไดนามิกอาร์เรย์ (Dynamic Array) เก็บค่าที่คำนวณไว้ก่อนหน้า ลูปผ่านอาร์เรย์และคำนวณเหรียญน้อยที่สุดที่ใช้ได้ หากคำนวณแล้วจะนำค่าจากไดนามิกอาร์เรย์มาใช้

Time Complexity: O(N)

Space Complexity: 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.Length);
    Console.WriteLine(ss);
}

ผลลัพธ์

3

หมายเหตุ: โค้ดต้นฉบับมีข้อผิดพลาดเล็กน้อย (ใช้ coins.Count() แทน coins.Length และลูป i < n แทน i <= n) โค้ดข้างต้นได้แก้ไขให้ถูกต้องแล้ว