C Program for Coin Change using Dynamic Programming (Memoization)
The above recursive solution has Optimal Substructure and Overlapping Subproblems so Dynamic programming (Memoization) can be used to solve the problem. So 2D array can be used to store results of previously solved subproblems.
Step-by-step approach:
- Create a 2D dp array to store the results of previously solved subproblems.
- dp[i][j] will represent the number of distinct ways to make the sum j by using the first i coins.
- During the recursion call, if the same state is called more than once, then we can directly return the answer stored for that state instead of calculating again.
Below is the implementation of the above approach:
C
#include <stdio.h>int N, SUM;// Recursive function to count the number of distinct ways// to make the sum by using n coinsint count(int coins[], int n, int sum, int dp[N + 1][SUM + 1]){ // Base Case if (sum == 0) return dp[n][sum] = 1; // If the number of coins is 0 or the sum is less than // 0, there is no way to make the sum. if (n == 0 || sum < 0) return 0; // If the subproblem is previously calculated, then // return the result if (dp[n][sum] != -1) return dp[n][sum]; // Two options for the current coin return count(coins, n, sum - coins[n - 1], dp) + count(coins, n - 1, sum, dp);}int main(){ int tc = 1; while (tc--) { int n, sum; n = 4; sum = 10; int coins[] = { 2, 5, 3, 6 }; int dp[n + 1][sum + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= sum; j++) { dp[i][j] = -1; } } N = n, SUM = sum; int res = count(coins, n, sum, dp); printf("%d\n", res); } return 0;} |
5
Time Complexity: O(N*sum), where N is the number of coins and sum is the target 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