https://www.hackerrank.com/challenges/coin-change
Checkout my solution to this hard Dynamic Programming from Hackerrank:
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int comp (const void * elem1, const void * elem2)
{
int f = *((int*)elem1);
int s = *((int*)elem2);
if (f > s) return 1;
if (f < s) return -1;
return 0;
}
int main(){
int n,m,i,j;
scanf("%ld %ld", &n,&m);
long int a[m],b[n+1];
b[0]=1;
for(i=1;i<(n+1);i++){
b[i]=0;
}
for(i=0;i<m;i++)
scanf("%ld",&a[i]);
qsort(a, sizeof(a)/sizeof(*a), sizeof(*a), comp);
for(i=0;i<m;i++){
for(j=a[i];j<n+1;j++)
b[j]+=b[j-a[i]];
}
printf("%ld",b[n]);
return 0;
}
