031.cpp

Go to the documentation of this file.

#include <iostream>

int array[] = {1,2,5,10,20,50,100,200};

unsigned sum=0;

//dynamic programming
void remainder(int N, int idx)
{
        N-= array[idx];

        if (N==0){
                sum++;
        }
        else if (N<0)
                return;
        else {
                for (int i=idx;i>=0;i--)
                        remainder(N,i);
        }
}

int main()
{
        for (int i=7;i>=0;i--)
        remainder(200,i);

        std::cout<<sum<<std::endl;
        return 0;
}