C++ coin change program

A coin change problem in C++ involves finding the number of ways to make change for a given amount of money using a set of coin denominations. Here’s a C++ program to solve the coin change problem using dynamic programming:

#include <iostream>
#include <vector>

// Function to find the number of ways to make change
int coinChangeWays(const std::vector<int>& coins, int amount) {
    int n = coins.size();
    std::vector<int> dp(amount + 1, 0);

    // There is one way to make change for amount = 0, which is by not using any coins.
    dp[0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }

    return dp[amount];
}

int main() {
    std::vector<int> coins = {1, 2, 5}; // Coin denominations
    int amount = 5; // Target amount to make change for

    int ways = coinChangeWays(coins, amount);

    std::cout << "Number of ways to make change for " << amount << " cents: " << ways << std::endl;

    return 0;
}

In this program:

1. We define a function coinChangeWays that takes a vector of coin denominations (coins) and an integer amount as input.
2. We create a dynamic programming array dp of size amount + 1, initialized to all zeros. dp[i] represents the number of ways to make change for i cents.
3. We set dp[0] to 1 because there is one way to make change for 0 cents (by not using any coins).
4. We use a nested loop to iterate through the coin denominations and update the dp array. For each coin denomination coins[i], we update dp[j] for all j from coins[i] to amount. We do this by adding the number of ways to make change for j - coins[i] to the number of ways to make change for j.
5. Finally, we return dp[amount], which represents the number of ways to make change for the given amount using the given coin denominations.

In the main function, we define the coin denominations and the target amount (coins and amount), and then we call the coinChangeWays function to find the number of ways to make change for the given amount.