# C++ Brute Force and Dynamic Programming

• Approach #1 Brute Force [Time Limit Exceeded]

Try every possible path by DFS.

Time complexity: O(2^n)

``````class Solution {
public:
int minCost(vector<vector<int>>& costs) {
if(costs.empty()) return 0;
int n = costs.size();
int c = costs[0].size();
return min(helper(costs, n, 0, 0), min(helper(costs, n, 1, 0), helper(costs, n, 2, 0)));
}
int helper(vector<vector<int>>& costs, int n, int idx, int row) {
if(row == (n - 1)) {
return costs[row][idx];
}
if(idx == 0) {
return costs[row][idx] + min(helper(costs, n, 1, row + 1), helper(costs, n, 2, row + 1));
}
if(idx == 1) {
return costs[row][idx] + min(helper(costs, n, 0, row + 1), helper(costs, n, 2, row + 1));
}
if(idx == 2) {
return costs[row][idx] + min(helper(costs, n, 0, row + 1), helper(costs, n, 1, row + 1));
}
}
};
``````

Approach #2 (Dynamic Programming) [Accepted]

We can use the dynamic programming method to eliminate duplicate paths that have been explored.

Time complexity: O(n)

``````class Solution {
public:
int minCost(vector<vector<int>>& costs) {
if(costs.empty()) return 0;
int n = costs.size();
vector<vector<int>> dp(n, vector<int>(3, 0));
dp[0][0] = costs[0][0];
dp[0][1] = costs[0][1];
dp[0][2] = costs[0][2];
for(int i = 1; i < n; i++) {
dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]);
dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2]);
dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1]);
}
return min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2]));
}
};
``````

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