2018-01-22 如果我们有面值为1元、3元和5元的硬币若干

算法动态规划:
http://blog.csdn.net/u013445530/article/details/45645307

void test3(){
    //1,3,5
    printf("%d\n",maxCount(26));
}

int maxCount(int n){
    int a[] = {1,3,5};
    int *p = (int*)malloc(sizeof(int)*(n+1));

    for(int i = 0;i<n+1;i++) *(p+i) = i;

    for(int i = 1;i<n+1;i++){
        for(int j = 0;j < 3;j++){
            if(i >= a[j]  && *(p+i-a[j]) + 1 < *(p+i))
            {
                *(p+i) = *(p+i-a[j]) + 1;
            }
        }
    }

    int result = *(p+n);
    free(p);
    return result;
}

求 第n个数的最小组成个数,就是求 n-[1,3,5) 之前的最小组成个数 +1:
比如求组成5 的最小个数:
拿一个1 元硬币, 是 4元的最小组成个数+1 ==4+1= 5
拿一个3元的硬币,是 2 元的最小组成个数+1 == 2+1 =3
拿一个5元的硬币,是0 元的最小组成个数+1 == 0 + 1 =1