C++ Brute Force and Dynamic Programming


  • 0
    T

    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]));
        }
    };
    

Log in to reply
 

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