Simple C++ DP Solution: O(n) Time & O(1) Space


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

Log in to reply
 

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