#money is an integer value
GreedyChange=function(money){
  coins=c(1,2,5,10,50) # coin vector
  change=NULL #used coins. It is a vector
  while(money>0){
    coin=max(coins[coins<=money]) #coins[coins<=money] select the values in coins lower than or equal to money
    change=c(change,coin)
    money=money-coin
  }
  return(change)
}

#money is integer value and coins a integer vector
RecursiveChange=function(money,coins){
if (money==0)
  return(0)
MinNumCoins=.Machine$integer.max 
for (coin_i in coins){ #coin_i slides the coins elements
  if (money>=coin_i){
    NumCoins=RecursiveChange(money-coin_i,coins)
    if (NumCoins+1<MinNumCoins)
      MinNumCoins=NumCoins+1
    }
}
return(MinNumCoins)
}

RecursiveChangeMod=function(money,coins){
  if (money==0)
    return(list(0,NULL))
  MinNumCoins=.Machine$integer.max #it is a integer value
  UsedCoins=NULL #it is used to store the used coins. It is an integer vector 
  for (coin_i in coins){
    if (money>=coin_i){
      Res=RecursiveChangeMod(money-coin_i,coins)
      if (Res[[1]]+1<MinNumCoins){
        MinNumCoins=Res[[1]]+1
        UsedCoins=c(Res[[2]],coin_i)
      }
    }
  }
  return(list(MinNumCoins,UsedCoins))
}


DPChange=function(money,coins){
  MinNumCoins=rep(0,money+1)
  for (m in {2:(money+1)}){ #m starts from 2 because R vector indexes starts from 1 
    MinNumCoins[m]=.Machine$integer.max
    for (coin_i in coins){
      if (m-1>=coin_i){
        if ((MinNumCoins[m-coin_i]+1) <MinNumCoins[m]){
            MinNumCoins[m]=MinNumCoins[m-coin_i]+1
        }
      }
    }
  }
return(MinNumCoins)
}


#system.time(RecursiveChange(30,c(1,2,5,10)))
#system.time(DPChange(5000,c(1,2,5,10)))