The Coin Change Problem | Editorial by aksingh007

An efficient solution to this problem is DP.
**Optimal Substructure**
1) Solutions that do not contain mth coin (or Sm).
2) Solutions that contain at least one Sm.
Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).

```
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

static long getWays(long n, long[] coins){
        int m=coins.length;
        long table[][]=new long[(int)n+1][m];
        for(int i=0;i<m;i++)
            table[0][i]=1;
        for(int i=1;i<n+1;i++){
            for(int j=0;j<m;j++){
                long x=0,y=0;
                if(i-(int)coins[j]>=0){           //INCLUDING Jth COIN
                    x=table[i-(int)coins[j]][j];
                }
                if(j-1>=0)
                    y=table[i][j-1];
                table[i][j]=x+y;
            }
        }
       return table[(int)n][(int)m-1];
    }

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        long[] c = new long[m];
        for(int c_i=0; c_i < m; c_i++){
            c[c_i] = in.nextLong();
        }
        // Print the number of ways of making change for 'n' units using coins having the values given by 'c'
        long ways = getWays(n, c);
        System.out.println(ways);
    }
}

```

The Coin Change Problem | Editorial by aksingh007

Download submission

All caught up!

View submission

Is your resume even shortlisted?