Coin Change (Sikkə Dəyişmə)

Problem Təsviri

Müxtəlif nominal dəyərli sikkələriniz var və müəyyən bir məbləğ əldə etməlisiniz. Minimum neçə sikkə istifadə etməlisiniz? Hər sikkə növündən istədiyiniz qədər istifadə edə bilərsiniz.

Məsələn:

Sikkələr: [1, 2, 5], Məbləğ: 11
- Cavab: 3 sikkə (5 + 5 + 1)
Sikkələr: [2], Məbləğ: 3
- Cavab: -1 (mümkün deyil)
Sikkələr: [1, 3, 4], Məbləğ: 6
- Cavab: 2 sikkə (3 + 3)

Recurrence Relation:

dp[amount] = min(dp[amount - coin] + 1) for all coins

Müxtəlif Yanaşmalar

1. Sadə Rekursiya (Naive Approach)

Koda bax

public class CoinChangeNaive {
    
    public static int coinChange(int[] coins, int amount) {
        // Base cases
        if (amount == 0) {
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        
        int minCoins = Integer.MAX_VALUE;
        
        // Try using each coin
        for (int coin : coins) {
            int result = coinChange(coins, amount - coin);
            
            // If valid solution found
            if (result >= 0 && result < minCoins) {
                minCoins = result + 1;
            }
        }
        
        return minCoins == Integer.MAX_VALUE ? -1 : minCoins;
    }
    
    public static void main(String[] args) {
        System.out.println("Coin Change (Naive Recursion):");
        
        int[] coins1 = {1, 2, 5};
        System.out.println("Coins: [1, 2, 5], Amount: 11");
        System.out.println("Minimum coins: " + coinChange(coins1, 11));
        
        int[] coins2 = {2};
        System.out.println("\nCoins: [2], Amount: 3");
        System.out.println("Minimum coins: " + coinChange(coins2, 3));
        
        int[] coins3 = {1, 3, 4};
        System.out.println("\nCoins: [1, 3, 4], Amount: 6");
        System.out.println("Minimum coins: " + coinChange(coins3, 6));
    }
}

Mürəkkəblik:

Time Complexity: O(S^n) - S: məbləğ, n: sikkə sayı (Eksponensial)
Space Complexity: O(n) - Rekursiya stack-i

Problemlər:

Çox yavaş böyük məbləğlər üçün
Eyni alt-problemlər dəfələrlə hesablanır

2. Memoization (Top-Down DP)

Koda bax

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class CoinChangeMemoization {
    
    // Using HashMap for memoization
    private static Map<Integer, Integer> memo;
    private static int[] coins;
    
    public static int coinChange(int[] coinArray, int amount) {
        coins = coinArray;
        memo = new HashMap<>();
        
        int result = coinChangeHelper(amount);
        return result == Integer.MAX_VALUE ? -1 : result;
    }
    
    private static int coinChangeHelper(int amount) {
        // Base cases
        if (amount == 0) {
            return 0;
        }
        if (amount < 0) {
            return Integer.MAX_VALUE;
        }
        
        // Check if already computed
        if (memo.containsKey(amount)) {
            return memo.get(amount);
        }
        
        int minCoins = Integer.MAX_VALUE;
        
        // Try each coin
        for (int coin : coins) {
            int result = coinChangeHelper(amount - coin);
            if (result != Integer.MAX_VALUE) {
                minCoins = Math.min(minCoins, result + 1);
            }
        }
        
        memo.put(amount, minCoins);
        return minCoins;
    }
    
    // Alternative implementation with array
    public static int coinChangeArray(int[] coins, int amount) {
        int[] memo = new int[amount + 1];
        Arrays.fill(memo, -2); // -2: not computed, -1: impossible
        
        int result = coinChangeHelperArray(coins, amount, memo);
        return result;
    }
    
    private static int coinChangeHelperArray(int[] coins, int amount, int[] memo) {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        
        if (memo[amount] != -2) {
            return memo[amount];
        }
        
        int minCoins = Integer.MAX_VALUE;
        
        for (int coin : coins) {
            int result = coinChangeHelperArray(coins, amount - coin, memo);
            if (result >= 0 && result < minCoins) {
                minCoins = result + 1;
            }
        }
        
        memo[amount] = (minCoins == Integer.MAX_VALUE) ? -1 : minCoins;
        return memo[amount];
    }
    
    public static void main(String[] args) {
        System.out.println("Coin Change (Memoization):");
        
        int[] coins1 = {1, 2, 5};
        System.out.println("Coins: [1, 2, 5], Amount: 11");
        System.out.println("Minimum coins: " + coinChange(coins1, 11));
        
        int[] coins2 = {2};
        System.out.println("\nCoins: [2], Amount: 3");
        System.out.println("Minimum coins: " + coinChange(coins2, 3));
        
        int[] coins3 = {186, 419, 83, 408};
        System.out.println("\nCoins: [186, 419, 83, 408], Amount: 6249");
        long startTime = System.currentTimeMillis();
        System.out.println("Minimum coins: " + coinChange(coins3, 6249));
        long endTime = System.currentTimeMillis();
        System.out.println("Vaxt: " + (endTime - startTime) + " ms");
    }
}

Mürəkkəblik:

Time Complexity: O(S * n) - S: məbləğ, n: sikkə sayı
Space Complexity: O(S) - Memo table və rekursiya stack-i

3. Tabulation (Bottom-Up DP)

Koda bax

import java.util.Arrays;

public class CoinChangeTabulation {
    
    public static int coinChange(int[] coins, int amount) {
        // Create DP table
        int[] dp = new int[amount + 1];
        
        // Initialize with maximum value (impossible)
        Arrays.fill(dp, amount + 1);
        
        // Base case: 0 amount needs 0 coins
        dp[0] = 0;
        
        // Fill table bottom-up
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        // If dp[amount] is still amount + 1, it's impossible
        return dp[amount] > amount ? -1 : dp[amount];
    }
    
    // Alternative: coin-first approach
    public static int coinChangeCoinFirst(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        // For each coin
        for (int coin : coins) {
            // Update all amounts that can be made with this coin
            for (int i = coin; i <= amount; i++) {
                if (dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
    
    // Method to show DP table
    public static void showDPTable(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        System.out.println("DP Table for coins " + Arrays.toString(coins) + ":");
        System.out.print("Amount: ");
        for (int i = 0; i <= amount; i++) {
            System.out.printf("%4d", i);
        }
        System.out.println();
        System.out.print("Coins:  ");
        for (int i = 0; i <= amount; i++) {
            if (dp[i] > amount) {
                System.out.print("  -1");
            } else {
                System.out.printf("%4d", dp[i]);
            }
        }
        System.out.println("\n");
    }
    
    public static void main(String[] args) {
        System.out.println("Coin Change (Tabulation):");
        
        int[] coins1 = {1, 2, 5};
        System.out.println("Coins: [1, 2, 5], Amount: 11");
        System.out.println("Minimum coins: " + coinChange(coins1, 11));
        
        showDPTable(coins1, 11);
        
        int[] coins2 = {1, 3, 4};
        System.out.println("Coins: [1, 3, 4], Amount: 6");
        System.out.println("Minimum coins: " + coinChange(coins2, 6));
        
        // Performance test
        long startTime = System.currentTimeMillis();
        int result = coinChange(coins1, 10000);
        long endTime = System.currentTimeMillis();
        
        System.out.println("\nAmount: 10000, Minimum coins: " + result);
        System.out.println("Vaxt: " + (endTime - startTime) + " ms");
    }
}

Mürəkkəblik:

Time Complexity: O(S * n) - S: məbləğ, n: sikkə sayı
Space Complexity: O(S) - DP table üçün

4. Path Reconstruction (Konkret Həll)

Koda bax

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CoinChangeWithPath {
    
    public static class Result {
        int minCoins;
        List<Integer> coins;
        
        Result(int minCoins, List<Integer> coins) {
            this.minCoins = minCoins;
            this.coins = coins;
        }
    }
    
    public static Result coinChangeWithCoins(int[] coins, int amount) {
        // DP table
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        
        // Parent array to track which coin was used
        int[] parent = new int[amount + 1];
        Arrays.fill(parent, -1);
        
        // Fill DP table
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i && dp[i - coin] + 1 < dp[i]) {
                    dp[i] = dp[i - coin] + 1;
                    parent[i] = coin;
                }
            }
        }
        
        // If impossible
        if (dp[amount] > amount) {
            return new Result(-1, new ArrayList<>());
        }
        
        // Reconstruct path
        List<Integer> usedCoins = new ArrayList<>();
        int currentAmount = amount;
        
        while (currentAmount > 0) {
            int coinUsed = parent[currentAmount];
            usedCoins.add(coinUsed);
            currentAmount -= coinUsed;
        }
        
        return new Result(dp[amount], usedCoins);
    }
    
    public static void main(String[] args) {
        System.out.println("Coin Change with Path Reconstruction:");
        
        int[] coins1 = {1, 2, 5};
        int amount1 = 11;
        Result result1 = coinChangeWithCoins(coins1, amount1);
        
        System.out.println("Coins: [1, 2, 5], Amount: 11");
        System.out.println("Minimum coins: " + result1.minCoins);
        System.out.println("Coins used: " + result1.coins);
        
        int[] coins2 = {1, 3, 4};
        int amount2 = 6;
        Result result2 = coinChangeWithCoins(coins2, amount2);
        
        System.out.println("\nCoins: [1, 3, 4], Amount: 6");
        System.out.println("Minimum coins: " + result2.minCoins);
        System.out.println("Coins used: " + result2.coins);
    }
}

Mürəkkəblik:

Time Complexity: O(S * n)
Space Complexity: O(S) - DP və parent array-ləri

5. Coin Change 2 (Kombinasiya Sayı)

Koda bax

import java.util.Arrays;

public class CoinChange2 {
    
    // LeetCode 518: Coin Change 2
    // Verilmiş məbləği əldə etmək üçün neçə fərqli yol var?
    
    public static int change(int amount, int[] coins) {
        // dp[i] = i məbləğini əldə etmək üçün yolların sayı
        int[] dp = new int[amount + 1];
        dp[0] = 1; // 0 məbləğini əldə etməyin 1 yolu var (heç bir sikkə istifadə etməmək)
        
        // Hər sikkə üçün
        for (int coin : coins) {
            // Bütün məbləğləri yenilə
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        
        return dp[amount];
    }
    
    // With 2D DP (more intuitive)
    public static int change2D(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        
        // Base case: 0 məbləğ üçün 1 yol var
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                // Don't use current coin
                dp[i][j] = dp[i - 1][j];
                
                // Use current coin (if possible)
                if (coins[i - 1] <= j) {
                    dp[i][j] += dp[i][j - coins[i - 1]];
                }
            }
        }
        
        return dp[n][amount];
    }
    
    public static void main(String[] args) {
        System.out.println("Coin Change 2 (Combination Count):");
        
        int[] coins1 = {1, 2, 5};
        System.out.println("Coins: [1, 2, 5], Amount: 5");
        System.out.println("Number of ways: " + change(5, coins1));
        
        int[] coins2 = {2};
        System.out.println("\nCoins: [2], Amount: 3");
        System.out.println("Number of ways: " + change(3, coins2));
        
        int[] coins3 = {1, 2, 5};
        System.out.println("\nCoins: [1, 2, 5], Amount: 11");
        System.out.println("Number of ways: " + change(11, coins3));
    }
}

Mürəkkəblik:

Time Complexity: O(S * n)
Space Complexity: O(S) - 1D DP

Performance Müqayisəsi

Koda bax

public class CoinChangeComparison {
    
    public static void comparePerformance() {
        int[] coins = {1, 2, 5};
        int[] amounts = {10, 20, 50, 100, 500};
        
        System.out.println("Performance Müqayisəsi:");
        System.out.println("Amount\tNaive\t\tMemo\t\tTabulation");
        
        for (int amount : amounts) {
            System.out.print(amount + "\t");
            
            // Naive (only for small amounts)
            if (amount <= 20) {
                long start = System.nanoTime();
                CoinChangeNaive.coinChange(coins, amount);
                long end = System.nanoTime();
                System.out.print((end - start) / 1000 + "μs\t\t");
            } else {
                System.out.print("Too slow\t");
            }
            
            // Memoization
            long start = System.nanoTime();
            CoinChangeMemoization.coinChange(coins, amount);
            long end = System.nanoTime();
            System.out.print((end - start) / 1000 + "μs\t\t");
            
            // Tabulation
            start = System.nanoTime();
            CoinChangeTabulation.coinChange(coins, amount);
            end = System.nanoTime();
            System.out.print((end - start) / 1000 + "μs");
            
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        comparePerformance();
    }
}

Müsahibə Sualları

1. Minimum Sikkə Sayı

Sual: Verilmiş məbləği əldə etmək üçün minimum sikkə sayını tapın. LeetCode: Problem 322 - Coin Change

2. Kombinasiya Sayı

Sual: Verilmiş məbləği əldə etmək üçün neçə fərqli kombinasiya var? LeetCode: Problem 518 - Coin Change 2

3. Konkret Həll

Sual: Yalnız minimum sayı deyil, hansı sikkələrin istifadə edildiyini göstərin. Cavab: Parent array ilə path reconstruction

4. Məhdud Sikkələr

Sual: Hər sikkədən yalnız müəyyən sayda istifadə edə bilərsinizsə? Cavab: 2D DP - dp[i][j] = coin i istifadə edərək j məbləği

5. Maksimum/Minimum Kombinasiya

Sual: Minimum və ya maksimum sayda sikkə istifadə edərək kombinasiya sayını tapın. Cavab: DP-də həm count, həm də ways saxlamaq

LeetCode Problemləri

322. Coin Change - https://leetcode.com/problems/coin-change/ (Minimum sikkə sayı)
518. Coin Change 2 - https://leetcode.com/problems/coin-change-2/ (Kombinasiya sayı)
377. Combination Sum IV - https://leetcode.com/problems/combination-sum-iv/ (Permutasiya sayı)
279. Perfect Squares - https://leetcode.com/problems/perfect-squares/ (Oxşar pattern)
983. Minimum Cost For Tickets - https://leetcode.com/problems/minimum-cost-for-tickets/ (Variation of coin change)

Real-World Tətbiqləri

Financial Systems: Pul vermə maşınlarında optimal sikkə/əskinas bölgüsü
Currency Exchange: Valyuta mübadiləsində optimal əməliyyat sayı
Resource Management: Məhdud resurslarla məqsədə çatma
Game Development: Oyun içi valyuta sistemi optimizasiyası
Inventory Management: Müxtəlif ölçülü paketlərlə sifariş doldurma

Optimizasiya Məsləhətləri

Sikkələri sıralamaq: Bəzən erkən dayandırma imkanı verir
Greedy olmur: Greedy approach (ən böyük sikkədən başlamaq) həmişə işləmir
Space optimization: 1D DP kifayətdir, 2D lazım deyil
Early termination: dp[amount] məbləğdən böyükdürsə, impossible
Coin-first vs Amount-first: Problem növündən asılı olaraq seçmək

Əlaqəli Problemlər

Unbounded Knapsack
Partition Equal Subset Sum
Target Sum
Combination Sum
Perfect Squares

Problem Təsviri​

Müxtəlif Yanaşmalar​

1. Sadə Rekursiya (Naive Approach)​

2. Memoization (Top-Down DP)​

3. Tabulation (Bottom-Up DP)​

4. Path Reconstruction (Konkret Həll)​

5. Coin Change 2 (Kombinasiya Sayı)​

Performance Müqayisəsi​

Müsahibə Sualları​

1. Minimum Sikkə Sayı​

2. Kombinasiya Sayı​

3. Konkret Həll​

4. Məhdud Sikkələr​

5. Maksimum/Minimum Kombinasiya​

LeetCode Problemləri​

Real-World Tətbiqləri​

Optimizasiya Məsləhətləri​

Əlaqəli Problemlər​

Problem Təsviri

Müxtəlif Yanaşmalar

1. Sadə Rekursiya (Naive Approach)

2. Memoization (Top-Down DP)

3. Tabulation (Bottom-Up DP)

4. Path Reconstruction (Konkret Həll)

5. Coin Change 2 (Kombinasiya Sayı)

Performance Müqayisəsi

Müsahibə Sualları

1. Minimum Sikkə Sayı

2. Kombinasiya Sayı

3. Konkret Həll

4. Məhdud Sikkələr

5. Maksimum/Minimum Kombinasiya

LeetCode Problemləri

Real-World Tətbiqləri

Optimizasiya Məsləhətləri

Əlaqəli Problemlər