Dynamic programming solves problems by combining optimal substructures. For the coin change problem, we need to find the minimum number of coins to make up a given amount.

Approach 1: Coin Selection as Subproblem

Create a 2D table where rows reprseent available coins and columns represent target amounts. Each cell dp[i][j] stores the minimum coins needed using the first i coins to make amount j.

public int minCoins(int[] coins, int amount) {
    int[][] dp = new int[coins.length + 1][amount + 1];
    
    // Initialize base case
    for (int j = 1; j <= amount; j++) {
        dp[0][j] = Integer.MAX_VALUE; // Impossible with no coins
    }
    
    for (int i = 1; i <= coins.length; i++) {
        for (int j = 1; j <= amount; j++) {
            if (coins[i-1] > j) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = Math.min(dp[i-1][j], 1 + dp[i][j - coins[i-1]]);
            }
        }
    }
    return dp[coins.length][amount];
}

Approach 2: Amount as Subproblem

Build a 1D array where dp[i] represents the minimum coins needed for amount i. Initialize with base cases and fill the array bottom-up.

public int minCoinsOptimized(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0; // Base case: 0 coins needed for 0 amount
    
    for (int coin : coins) {
        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];
}

Both approaches efficiently solve the problem using dynamic programming principles, with the second method offering better space complexity.