coins = [1,5,10,25,50]

ways a con = ways' a coins con where
  ways' 0 _  con = con 1
  ways' _ [] con = con 0
  ways' a (c:cs) con | a<c = con 0 
                     | otherwise = ways' (a-c) (c:cs) (\c1 -> ways' a cs (\c2 -> con (c1+c2)))

main = ways 100 print

coins = [1,5,10,25,50]

DM>ways a con = ways' a coins con where
DM>  ways' 0 _  con = con 1
DM>  ways' _ [] con = con 0
DM>  ways' a (c:cs) con | a<c = con 0 
DM>                     | otherwise = ways' (a-c) (c:cs) (\c1 -> ways' a cs (\c2 -> con (c1+c2)))

DM>main = ways 100 print
DM>

DM>Для 100 выводит верный ответ. На 1000 задумался, съел больше гига памяти (сколько было свободно), результата я не дождался.

ways' 1000 coins print =
ways' 999 coins (\x1->...print) =
ways' 998 coins (\x2->...(\x1->...print)) =
.....
ways' 0 coins (\x1000->.....(\x2->...(\x1->...print))...) =

let coins = [|1;5;10;25;50|]

let rec cc amount kinds con =
  if kinds = 0 || amount = 0 then con 1 else
  if amount < 0 then con 0 else
  cc amount (kinds-1) (fun c1 -> cc (amount - coins.[kinds]) kinds (fun c2 -> con (c1+c2)))
  
cc 2000 4 (printfn "%d")

v=.0:`1:`(1:`(($:}.)+((-{.)$:]))@.(1:<#@]))@.(1:+*@[)
2000 v 50 25 10 5 1

ways _ 0 = 1
ways [] _ = 0
ways (c:cs) s = sum [ways cs (s-m) | m <- [0, c .. s]]

main = do putStrLn $ show $ ways [1,5,10,25,50] 2000

ways _ 0 = 1
ways [] _ = 0
ways cs s | noSolve cs s = 0  -- нет смысла копать глубже, решений нет
ways (c:cs) s = sum [ways cs (s-m) | m <- [0, c .. s]]

noSolve cs s = rem s (foldl1 gcd cs) /= 0  -- true, если не существует решений диофантова уравнения с коэффициентами cs и свободным членом s

main = do putStrLn $ show $ ways [1,5,10,25,50] 2000

let foldl1 f lst = match lst with 
  | [] -> failwith "empty list in foldl1"
  | x::xs -> List.fold_left f x xs;;

let rec gcd a b = if b = 0 then a else gcd b (a mod b);;

let nosolve cs s = s mod (foldl1 gcd cs) <> 0;;

let rec ways s coins = 
  if s = 0 then 1 else
  match coins with
  | [] -> 0
  | cs when nosolve cs s -> 0
  | c::cs -> Enum.fold (+) 0 (Enum.init (s/c + 1) (fun i-> ways (s-i*c) cs));; 

print_int (ways 2000 [1;5;10;25;50]);;

(defun cc-5 (amount coins)
  (labels ((make-tagged-amount (kinds amount)
         (cons kinds amount))
       
       (get-kinds (tagged-amount)
         (car tagged-amount))
       
       (get-amount (tagged-amount)
         (cdr tagged-amount))

       (merge-tagged-amount-lists (a b result)
         (if (and a b)
         (let ((amount-a (get-amount (car a)))
               (amount-b (get-amount (car b))))
           (cond ((< amount-a amount-b) (merge-tagged-amount-lists (cdr a) b (cons (car a) result)))
             ((> amount-a amount-b) (merge-tagged-amount-lists a (cdr b) (cons (car b) result)))
             ((= amount-a amount-b)
              (merge-tagged-amount-lists (cdr a)
                             (cdr b)
                             (cons (make-tagged-amount (+ (get-kinds (car a))
                                          (get-kinds (car b)))
                                           amount-a)
                               result)))))
         (if (or a b)
             (append (nreverse result) (or a b))
             (nreverse result))))
         
       (get-tagged-amount-list (kinds amount coin result)
         (cond ((> amount 0) (get-tagged-amount-list kinds
                             (- amount coin)
                             coin
                             (cons (make-tagged-amount kinds amount)
                                   result)))
           ((= amount 0) (cons (make-tagged-amount kinds amount)
                       result))
           (t result)))

       (sum (tagged-amount-list coin cur-sum result)        
         (if tagged-amount-list
         (let ((tagged-amount (car tagged-amount-list)))
           (cond ((= (get-amount tagged-amount) cur-sum) (sum tagged-amount-list
                                      coin
                                      (+ cur-sum coin)
                                      (+ result (get-kinds tagged-amount))))
             ((< (get-amount tagged-amount) cur-sum) (sum (cdr tagged-amount-list)
                                      coin
                                      cur-sum
                                      result))
             ((> (get-amount tagged-amount) cur-sum) (sum tagged-amount-list
                                      coin
                                      (+ cur-sum coin)
                                      result))))
         result))
            
       (process-coin (tagged-amount-list coins)
         (if (cdr coins)
         (process-coin (reduce #'(lambda (a b)
                       (merge-tagged-amount-lists a
                                      (get-tagged-amount-list (get-kinds b)
                                                  (get-amount b)
                                                  (car coins)
                                                  nil)
                                      nil))
                       (cdr tagged-amount-list)
                       :initial-value (get-tagged-amount-list (get-kinds (car tagged-amount-list))
                                          (get-amount (car tagged-amount-list))
                                          (car coins)
                                          nil))
                   (cdr coins))
         (sum tagged-amount-list (car coins) 0 0))))
    (if coins
    (process-coin (list (make-tagged-amount 1 amount)) coins)
    0)))

;; CL-USER> (time (cc-5 50000 '(50 25 10 5 1)))
;; Evaluation took:
;;   14.433 seconds of real time
;;   14.068879 seconds of user run time
;;   0.396025 seconds of system run time
;;   [Run times include 2.192 seconds GC run time.]
;;   0 calls to %EVAL
;;   0 page faults and
;;   2,790,509,272 bytes consed.
;; 4182519842501

#include <iostream>

// немножко чистоты типов - просто чтоб различать, кто есть ху
typedef int money_t; // суммы денег
typedef int count_t; // количество монет

// номиналы монет
money_t const coins[] =
#if 0
    { 1, 5, 10, 25, 50 };
#else
    { 50, 25, 10, 5, 1 }; // удобнее, когда крупными монетами вперёд - меньше промахов (а с учётом 1-копейки, их вообще нет)
#endif 
size_t const num_coins = _countof(coins);

// сумма, которую будем разменивать
money_t const target = 1000;

// переменная цикла состоит из
count_t amount[num_coins]; // кошелька (сколько монет каждого номинала?)
bool exact; // и признака, что в кошельке точная сумма

// процедура заполнения кошелька, начиная с монет номинала номер k
void complete(money_t sum, size_t const k)
{
    for(size_t i = k; i != num_coins; ++i)
    {
        money_t const coin = coins[i];
        amount[i] = sum / coin; // процедура детерминированная: заполняем данным номиналом по максимуму
        sum %= coin;
    }
    exact = sum==0;
}

// функция нахождения хвоста из нулей
size_t find_tail_zeros()
{
    // возвращает k : для всех i таких, что k<=i<n-1, a[i]==0
    
    size_t k = num_coins-1; // маленькая хитрость: не учитываем последний номинал (см.ниже)
    while(k > 0 && amount[k-1] == 0)
        --k;
    return k;
}

money_t sum_head(size_t const k)
{
    money_t sum = 0;
    for(size_t i = 0; i != k; ++i)
        sum += amount[i] * coins[i];
    return sum;
}

//////////////////
// первая итерация

void init()
{
    complete(target, 0); // просто заполняем кошелёк, получая лексикографический максимум
}

/////////////////////
// следующая итерация

bool next() // возвращает признак того, что итерация удалась
{
    // наша задача - получить лексикографического соседа (следующий по убыванию)

    size_t const k = find_tail();
    if(k==0)
        return false; // весь кошелёк состоит из нулей, скручивать нечего
    
    // скручиваем a[k] - даём хвосту шанс измениться
    --amount[k-1];
    
    // считаем, сколько у нас денег осталось на заполнение хвоста - и заполняем его
    complete(target - sum_head(k), k);
    
    return true;
}

int main()
{
    // ведём статистику: сколько всего итераций, и сколько из них успешных
    int attempts = 0, success = 0;
    for(bool go = (init(),true); go; go = next())
    {
        ++attempts;
        if(exact)
            ++success;

        // чтобы юзер не скучал...
#if 0
        std::cout << "попытка " << attempts << ": ";
        for(size_t i = 0; i != num_coins; ++i)
            std::cout << coins[i] << "*" << amount[i] << " ";
        if(exact)
            std::cout << "попал! " << success;
        std::cout << std::endl;
#else
        if(attempts % 100 == 0)
            std::cout << attempts << " попыток, " << success << " попаданий ...\r";
#endif
    }
    std::cout << std::endl;
    std::cout << attempts << " попыток, " << success << " попаданий" << std::endl;
}

#include <iostream>

const int coins[] = {50, 25, 10, 5, 1};

const size_t num_coins = sizeof(coins)/sizeof(int);

int amounts[num_coins];

int target = 100;

int main()
{
    int i = 0;
    int success = 0;
    amounts[0] = target;
    
    while (amounts[0] > 0)
    {

    if (amounts[i] > 0)
    {
        if (i < num_coins - 1)
        {
        amounts[i+1] = amounts[i];
        i++;
        }
        else
        amounts[i] -= coins[i];
    }
    else
    {
        if (amounts[i] == 0) ++success;
        if (i > 0)
        {
        i--;
        amounts[i] -= coins[i];
        }
    }
    }

    if (amounts[0] == 0)
    success++;

    std::cout << success << std::endl;
}

(defun cc-6 (amount coins)
  (let ((last_coin_index (1- (length coins)))
    (amounts (make-list (length coins) :initial-element 0)))

    (setf (elt amounts 0) amount)
    
    (labels ((iter (i result)
           (if (> (elt amounts i) 0)
           (progn
             (if (< i last_coin_index)
             (progn
               (setf (elt amounts (1+ i)) (elt amounts i)) ; i.e. amounts[i+1]=amounts[i]
               (iter (1+ i) result))
             (progn
               (decf (elt amounts i) (elt coins i))    ; i.e. amounts[i]-=coins[i]
               (iter i result))))
           (let ((dt (if (= (elt amounts i) 0) 1 0)))
             (if (> i 0)
             (progn
               (decf (elt amounts (1- i)) (elt coins (1- i))) ; i.e. amounts[i-1]-=coins[i-1]
               (iter (1- i) (+ result dt)))
             (+ result dt))))))
      (iter 0 0))))

;; CL-USER> (cc-6 1000 '(50 25 10 5 1))
;; 801451

hub>;(define (cc amount kinds-of-coins) 
hub>;  (cond ((= amount 0) 1) 
hub>;        ((or (< amount 0) (= kinds-of-coins 0)) 0) 
hub>;        (else (+ (cc amount (- kinds-of-coins 1)) 
hub>;                 (cc (- amount (first-denomination kinds-of-coins)) 
hub>;                     kinds-of-coins))))) 
hub>;

(define (cc amount kinds-of-coins count) 
   (cond ((= kinds-of-coins 1) 1)
         ((< amount 0) count)
         (else (cc (- amount (first-denomination kinds-of-coins))
                    kinds-of-coins 
                    (+ count (cc amount (- kinds-of-coins 1) 0))))))  

(define (count-change amount) 
   (cc amount 5 0))

> (count-change 1000)
801451