# Evolve from brute force to optimal

1. O(2^n), try all combinations
``````    int minCost(vector<vector<int>>& costs) {
return minCost(-1,-1,costs);
}
int minCost(int i, int j, vector<vector<int>>& costs) {
if(i==costs.size()) return 0;
int mc=INT_MAX;
for(int k=0;k<3;k++) if(k!=j) mc = min(mc, minCost(i+1,k,costs));
return i<0 ? mc : costs[i][j]+mc;
}
``````
1. O(n) memoization
``````    int minCost(vector<vector<int>>& costs) {
vector<vector<int>> mc(costs.size(),vector<int>(3));
return minCost(-1,-1,costs,mc);
}
int minCost(int i, int j, vector<vector<int>>& costs, vector<vector<int>>& mc) {
if(i==costs.size()) return 0;
if(i>=0 && mc[i][j]) return mc[i][j];
int cost=INT_MAX;
for(int k=0;k<3;k++) if(k!=j) cost = min(cost, minCost(i+1,k,costs,mc));
return i<0 ? cost : mc[i][j]=costs[i][j]+cost;
}
``````
1. O(n) dp
``````    int minCost(vector<vector<int>>& costs) {
int n = costs.size();
vector<vector<int>> dp(n,vector<int>(3,INT_MAX));
dp.push_back(vector<int>(3));
for(int i=n-1;i>=0;i--)
for(int j=0;j<3;j++) {
for(int k=0;k<3;k++)
if(k!=j) dp[i][j] = min(dp[i][j],dp[i+1][k]);
dp[i][j]+=costs[i][j];
}
return min(dp[0][0],min(dp[0][1],dp[0][2]));
}
``````
1. O(n) constant space dp. In #3, the current state is derived from the previous state only. So we don't need to cache all states.
``````    int minCost(vector<vector<int>>& costs) {
int mc[3] = {0};
for(auto &v:costs) {
int t0 = mc[0], t1 = mc[1];
mc[0] = v[0] + min(mc[1], mc[2]);
mc[1] = v[1] + min(t0, mc[2]);
mc[2] = v[2] + min(t0, t1);
}
return min(mc[0], min(mc[1], mc[2]));
}
``````

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