C Program for Coin Change using Dynamic Programming (Tabulation)
- Create a 2D dp array with rows and columns equal to the number of coin denominations and target sum.
dp[0][0]
will be set to
1
which represents the base case where the target sum is 0, and there is only one way to make the change by not selecting any coin.- Iterate through the rows of the dp array (i from 1 to
n
), representing the current coin being considered.
- The inner loop iterates over the target sums (
j
from 0 tosum
).
- Add the number of ways to make change without using the current coin, i.e.,
dp[i][j] += dp[i-1][j]
.- Add the number of ways to make change using the current coin, i.e.,
dp[i][j] += dp[i][j-coins[i-1]]
.dp[n][sum]
will contain the total number of ways to make change for the given target sum using the available coin denominations.
Below is the implementation of the above approach:
C
#include <stdio.h> // Returns total distinct ways to make sum using n coins of // different denominations int count( int coins[], int n, int sum) { // 2D dp array where n is the number of coin // denominations and sum is the target sum int dp[n + 1][sum + 1]; // Initialize the dp array for ( int i = 0; i <= n; i++) { for ( int j = 0; j <= sum; j++) { dp[i][j] = 0; } } // Represents the base case where the target sum is 0, // and there is only one way to make change: by not // selecting any coin dp[0][0] = 1; for ( int i = 1; i <= n; i++) { for ( int j = 0; j <= sum; j++) { // Add the number of ways to make change without // using the current coin dp[i][j] += dp[i - 1][j]; if ((j - coins[i - 1]) >= 0) { // Add the number of ways to make change // using the current coin dp[i][j] += dp[i][j - coins[i - 1]]; } } } return dp[n][sum]; } int main() { int coins[] = {2, 5, 3, 6}; int n = 4; int sum = 10; printf ( "%d\n" , count(coins, n, sum)); return 0; } |
Output
5
Time complexity : O(N*sum)
Auxiliary Space : O(N*sum)
C Program for Coin Change | DP-7
Write a C program for a given integer array of coins[ ] of size N representing different types of denominations and an integer sum, the task is to find the number of ways to make a sum by using different denominations.
Examples:
Input: sum = 4, coins[] = {1,2,3},
Output: 4
Explanation: there are four solutions: {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}.Input: sum = 10, coins[] = {2, 5, 3, 6}
Output: 5
Explanation: There are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}.
Contact Us