# Evolve from brute force to optimal, a review of all solutions

• This is similar to word break and perfect square

1. O(n^s) brute force
``````    int coinChange(vector<int>& coins, int amount) {
if(amount==0) return 0;
if(amount<0) return -1;
int cc = -1;
for(int i=0;i<coins.size();i++) {
int coin = coinChange(coins,amount-coins[i]);
if(coin>=0) cc = cc < 0 ? coin : min(cc,coin);
}
return cc <0 ? -1 : cc+1;
}
``````
1. O(ns) pseudo polynomial dfs with Memoization
``````    int coinChange(vector<int>& coins, int amount) {
unordered_map<int,int> mem;
return coinChange(amount,mem,coins);
}
int coinChange(int amount, unordered_map<int,int>& mem, vector<int>& coins) {
if(amount==0) return 0;
if(amount<0) return -1;
auto it = mem.find(amount);
if(it != mem.end()) return it->second;
int cc = amount+1;
for(int i=0;i<coins.size();i++) {
int coin = coinChange(amount-coins[i],mem,coins);
if(coin>=0) cc = min(cc,coin);
}
return mem[amount] = cc > amount ? -1 : cc+1;
}
``````
1. O(ns) pseudo polynomial dp
``````    int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1, amount+1);
dp[0]=0;
for(int i=0;i<=amount;i++)
for(int c:coins)
if(c<=i) dp[i] = min(dp[i],dp[i-c]+1);
return dp[amount]>amount? -1 : dp[amount];
}
``````
1. O(ns) traditional bfs with q and visited flag
``````    int coinChange(vector<int>& coins, int amount) {
unordered_set<int> vstd;
queue<int> q({0});
int cc=0;
while(!q.empty()) {
int n = q.size();
for(int i=0;i<n;i++) {
int a = q.front();
q.pop();
if(a==amount) return cc;
if(a>amount || vstd.count(a)) continue;
vstd.insert(a);
for(int c:coins) q.push(a+c);
}
cc++;
}
return -1;
}
``````
1. bfs that caches two levels only.
``````    int coinChange(vector<int>& coins, int amount) {
unordered_set<int> cur({0}), nxt, *p_cur=&cur,*p_nxt=&nxt;
int cc=0;
while(!p_cur->empty()) {
for(int a:*p_cur) {
if(a==amount) return cc;
if(a>amount) continue;
for(int c:coins) p_nxt->insert(a+c);
}
swap(p_cur,p_nxt);
p_nxt->clear();
cc++;
}
return -1;
}
``````
1. Two end bfs
``````    int coinChange(vector<int>& coins, int amount) {
unordered_set<int> begin({0}), end({amount}), nxt, vstd, *p_sm=&begin, *p_lg = &end, *p_nxt=&nxt;
int cc=0;
bool isBegin = 1;
while(!p_sm->empty() && !p_lg->empty()) {
if(p_sm->size()>p_lg->size()) {
swap(p_sm,p_lg);
isBegin = !isBegin;
}
for(int a:*p_sm) {
if(p_lg->count(a)) return cc;
if(a>amount) continue;
for(int c:coins) p_nxt->insert(isBegin?a+c:a-c);
}
swap(p_sm,p_nxt);
p_nxt->clear();
cc++;
}
return -1;
}
``````

I think dfs with memorization and bfs are better because they don't visit invalid states while test cases show that dp is the fastest.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.