C Program for Coin Change using the Space Optimized 1D array
In the above tabulation approach we are only using dp[i-1][j] and dp[i][j] etc, so we can do space optimization by only using a 1d dp array.
Step-by-step approach:
- Create a 1D dp array,
dp[i]represents the number of ways to make the sumiusing the given coin denominations. - The outer loop iterates over the coins, and the inner loop iterates over the target sums. For each
dp[j], it calculates the number of ways to make change using the current coin denomination and the previous results stored indp. dp[sum]contains the total number of ways to make change for the given target sum using the available coin denominations. This approach optimizes space by using a 1D array instead of a 2D DP table.
Below is the implementation of the above approach:
C
#include <stdio.h>#include <string.h>int count(int coins[], int n, int sum){ int dp[sum + 1]; memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i = 0; i < n; i++) { for (int j = coins[i]; j <= sum; j++) { dp[j] += dp[j - coins[i]]; } } return dp[sum];}int main(){ int coins[] = {2, 5, 3, 6}; int n = sizeof(coins) / sizeof(coins[0]); int sum = 10; printf("%d\n", count(coins, n, sum)); return 0;} |
5
Time complexity : O(N*sum)
Auxiliary Space : O(sum)
Please refer complete article on Coin Change | DP-7 for more details!
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