DSA/coinChange.cpp at main · Saquib504/DSA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
using namespace std;


// R E C U R S I O N + M E M O I Z A T I O N
//int f(int index, int target, vector<int>&coins, vector<vector<int>>&memo) {
//     if(index == 0){
//         if(target%coins[index] == 0){
//             return target/coins[index];
//         }else return 1e9;
//     }

//     if(memo[index][target] != -1) return memo[index][target];

//     int notTake = 0 + f(index-1, target, coins, memo);
//     int take = 1e9;

//     if(coins[index] <= target)
//         take = 1 + f(index, target - coins[index], coins, memo);


//     return memo[index][target] = min(notTake, take);
// }

// T A B U L A T I O N - M E T H O D
// int coinChange(vector<int>&coins, int amount) {
//     int n = coins.size();

//     vector<vector<int>>memo(n, vector<int>(amount+1, 0));

//     for(int target = 0; target <= amount; target++) {
//         if(target % coins[0] == 0){
//             memo[0][target] = target / coins[0];
//         }else memo[0][target] = 1e9;
//     }

//     for(int i = 1; i < n; i++) {
//         for(int target = 0; target <= amount; target++) {
//             int notTake = 0 + memo[i-1][target];

//             int take = 1e9;

//             if(coins[i] <= target) take = 1 + memo[i][target - coins[i]];

//             memo[i][target] = min(notTake, take);
//         }
//     }
//     return memo[n-1][amount];
// }

// S P A C E - O P T I M I Z A T I O N
int coinChange(vector<int>&coins, int amount) {
    int n = coins.size();

    vector<int>prev(amount+1, 0);
    vector<int>temp(amount+1, 0);

    for(int target = 0; target <= amount; target++) {
        if(target% coins[0] == 0) {
            prev[target] = target / coins[0];
        }else prev[target] = 1e9;
    }

    for(int i = 1; i < n; i++) {
        for(int target = 0; target <= amount; target++) {
            int notTake = 0 + prev[target];
            int take = INT_MAX;
            if(coins[i] <= target) take = 1 + temp[target - coins[i]];
            temp[target] = min(notTake, take);
        }
        prev = temp;
    }
    int ans = prev[amount];
    if(ans == 1e9) return -1;
    else return ans;
}


int main() {
    vector<int>coins = {7,5};
    int T = 11;

    cout << "The minimum number of coins required are : " << coinChange(coins, T) << endl;
    return 0;
}