/*
 * @file   CoinChange.h
 * @author (original JAVA) William Fiset, william.alexandre.fiset@gmail.com
 *         (conversion to C++) Armin Zare Zadeh, ali.a.zarezadeh@gmail.com
 * @date   15 July 2020
 * @version 0.1
 * @brief   The coin change problem is an unbounded knapsack problem variant. The problem asks you to find
 * the minimum number of coins required for a certain amount of change given the coin denominations.
 * You may use each coin denomination as many times as you please.
 *
 * <p>Tested against: https://leetcode.com/problems/coin-change/
 */

#ifndef D_COINCHANGE_H
#define D_COINCHANGE_H

#include <vector>
#include <deque>
#include <list>
#include <set>   // set and multiset
#include <map>   // map and multimap
#include <unordered_set>  // unordered set/multiset
#include <unordered_map>  // unordered map/multimap
#include <iterator>
#include <algorithm>
#include <numeric>    // some numeric algorithm
#include <functional>
#include <stack>

#include <sstream>
#include <memory>
#include <iostream>
#include <cmath>

namespace dsa {

class CoinChange {

private:
	static const int INF;
public:
  static int coinChange(const std::vector<int>& coins, int amount) {

    if (coins.size() == 0) throw std::invalid_argument("No coin values :/");

    int N = coins.size();
    // Initialize table and set first row to be infinity
    std::vector<std::vector<int>> DP(N + 1, std::vector<int>(amount + 1, INF));
    DP[1][0] = 0;

    // Iterate through all the coins
    for (int i = 1; i <= N; i++) {

      int coinValue = coins[i - 1];
      for (int j = 1; j <= amount; j++) {

        // Consider not selecting this coin
        DP[i][j] = DP[i - 1][j];

        // Try selecting this coin if it's better
        if (j - coinValue >= 0 && DP[i][j - coinValue] + 1 < DP[i][j])
          DP[i][j] = DP[i][j - coinValue] + 1;
      }
    }

    // The amount we wanted to make cannot be made :/
    if (DP[N][amount] == INF) return -1;

    // Return the minimum number of coins needed
    return DP[N][amount];
  }


   static int coinChangeSpaceEfficient(const std::vector<int>& coins, int amount) {

    if (coins.size() == 0) throw std::invalid_argument("Coins array is null");

    // Initialize table and set everything to infinity except first cell
    std::vector<int> DP(amount + 1, INF);
    DP[0] = 0;

    for (int i = 1; i <= amount; i++)
      for (int coinValue : coins)
        if (i - coinValue >= 0 && DP[i - coinValue] + 1 < DP[i]) DP[i] = DP[i - coinValue] + 1;

    // The amount we wanted to make cannot be made :/
    if (DP[amount] == INF) return -1;

    // Return the minimum number of coins needed
    return DP[amount];
  }

public:
  // The recursive approach has the advantage that it does not have to visit
  // all possible states like the tabular approach does. This can speedup
  // things especially if the coin denominations are large.
   static int coinChangeRecursive(const std::vector<int>& coins, int amount) {

    if (coins.size() == 0) throw std::invalid_argument("Coins array is null");
    if (amount < 0) return -1;

    std::vector<int> DP(amount + 1);
    return coinChangeRecursive(amount, coins, DP);
  }

private:
  // Private helper method to actually go the recursion
   static int coinChangeRecursive(int amount, const std::vector<int>& coins, std::vector<int>& DP) {

    // Base cases.
    if (amount < 0) return -1;
    if (amount == 0) return 0;
    if (DP[amount] != 0) return DP[amount];

    int minCoins = INF;
    for (int coinValue : coins) {

      int newAmount = amount - coinValue;
      int value = coinChangeRecursive(newAmount, coins, DP);
      if (value != -1 && value < minCoins) minCoins = value + 1;
    }

    // If we weren't able to find some coins to make our
    // amount then cache -1 as the answer.
    return DP[amount] = (minCoins == INF) ? -1 : minCoins;
  }

};
const int CoinChange::INF = 987654321;


void CoinChange_test()
{
  const std::vector<int> coins{2, 6, 1};
  std::cout << CoinChange::coinChange(coins, 17) << std::endl;
  std::cout << CoinChange::coinChangeSpaceEfficient(coins, 17) << std::endl;
  std::cout << CoinChange::coinChangeRecursive(coins, 17) << std::endl;
}

} // namespace dsa

#endif /* D_JOSEPHUSPROBLEM_H */
