Advertisement
informaticage

Coin change DP and REC

Nov 25th, 2022
1,027
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <functional>
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. #define MAX_VALUE 100000
  7. vector<int> DP(MAX_VALUE + 1, MAX_VALUE + 1);
  8.  
  9. template <typename Less, typename... T>
  10. constexpr auto& m_min(Less&& less, const T&... values) {
  11.   return std::min({ std::cref(values)..., }, std::forward<Less>(less)).get();
  12. }
  13.  
  14. int safe_access(vector<int> DP, int index) {
  15.   if (index < 0) {
  16.     return MAX_VALUE + 1;
  17.   }
  18.   return DP.at(index);
  19. }
  20.  
  21. void coin_change(int value) {
  22.   DP[0] = 1;
  23.   DP[1] = DP[5] = DP[10] = DP[20] = DP[100] = 1;
  24.  
  25.   for (int i = 1; i <= value; i++) {
  26.     DP[i] = m_min(
  27.       std::less<int>(),
  28.       safe_access(DP, i),
  29.       safe_access(DP, i - 1) + 1,
  30.       safe_access(DP, i - 5) + 1,
  31.       safe_access(DP, i - 10) + 1,
  32.       safe_access(DP, i - 20) + 1,
  33.       safe_access(DP, i - 100) + 1
  34.     );
  35.   }
  36.  
  37. }
  38.  
  39. int coin_change_rec(int value) {
  40.   if (value < 0) return MAX_VALUE + 1;
  41.   if (value == 0) return 0;
  42.   if (value == 1 || value == 5 || value == 10 || value == 20 || value == 100) {
  43.     return 1;
  44.   }
  45.  
  46.   return 1 + m_min(
  47.         std::less<int>(),
  48.         coin_change_rec(value - 1),
  49.         coin_change_rec(value - 5),
  50.         coin_change_rec(value - 10),
  51.         coin_change_rec(value - 20),
  52.         coin_change_rec(value - 100)
  53.       );
  54. }
  55.  
  56. int main() {
  57.   int value;
  58.   cin >> value;
  59.  
  60.   coin_change(value);
  61.   cout << DP.at(value);
  62.   return 0;
  63. }
Tags: dp
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement