DSA-LeetCode/CoinChange.cpp at master · jashanwarraich/DSA-LeetCode · 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
// Q178 https://www.codingninjas.com/codestudio/problems/630471?topList=striver-sde-sheet-problems&utm_source=striver&utm_medium=website

// Recursion
// Time: >O(2^n), Exponential
// Space: O(n)
#include<bits/stdc++.h>
int f(int ind, int tar,int * a){
        if(ind==0){
            return (tar%a[0]==0);
        }
        int nt=f(ind-1,tar,a);
        int t=0;
        if(a[ind]<=tar)
            t=f(ind,tar-a[ind],a);
        return t+nt;
 }

long countWaysToMakeChange(int *a, int n, int tar)
{
     return f(n-1,tar,a);
}

// Memorisation
// Time: O(N*m)
// Space: O(N*M)+O(N) = auxiliary stack space+ dp
#include<bits/stdc++.h>
long f(int ind, int tar,int * a,vector<vector<long>> &dp){
        if(ind==0){
            return (tar%a[0]==0);
        }
    if(dp[ind][tar]!=-1) return dp[ind][tar];
        long nt=f(ind-1,tar,a,dp);
        long t=0;
        if(a[ind]<=tar)
            t=f(ind,tar-a[ind],a,dp);
        return dp[ind][tar]=t+nt;
 }

long countWaysToMakeChange(int *a, int n, int tar)
{
    vector<vector<long>> dp(n,vector<long>(tar+1,-1));
     return f(n-1,tar,a,dp);
}

// DP
// Time: O(N*m)
// Space: O(N*M)
#include<bits/stdc++.h>

long countWaysToMakeChange(int *a, int n, int val)
{
    vector<vector<long>> dp(n,vector<long>(val+1,0));
    for(int j=0;j<val+1;j++) dp[0][j]=val%a[0]==0;
    for(int ind=1;ind<n;ind++){
        for(int tar=0;tar<=val;tar++){
            long nt=dp[ind-1][tar];
            long t=0;
            if(a[ind]<=tar)
                t=dp[ind][tar-a[ind]];
            dp[ind][tar]=t+nt;
        }
    }
     return dp[n-1][val];
}

// TABULATION
// Time: O(N*m)
// Space: O(2*M)
#include<bits/stdc++.h>

long countWaysToMakeChange(int *a, int n, int val)
{
    vector<long> p(val+1,0),c(val+1,0);
    for(int j=0;j<val+1;j++) p[j]=val%a[0]==0;
    for(int ind=1;ind<n;ind++){
        for(int tar=0;tar<=val;tar++){
            long nt=p[tar];
            long t=0;
            if(a[ind]<=tar)
                t=c[tar-a[ind]];
            c[tar]=t+nt;
        }
        p=c;
    }
     return p[val];
}