Sharing my 12ms C++ solution


  • 0
    T
    class Solution {
    public:
        int minCost(vector<vector<int>>& costs) {
            int n = costs.size();
            if (n==0)
            {
                return 0;
            }
            vector<int> DP(3*n, 0);
            DP[0] = costs[0][0];
            DP[1] = costs[0][1];
            DP[2] = costs[0][2];
            int i;
            for(i=1; i<n; i++)
            {
                DP[3*i+0] = costs[i][0] + min(DP[3*(i-1)+1], DP[3*(i-1)+2]);
                DP[3*i+1] = costs[i][1] + min(DP[3*(i-1)+0], DP[3*(i-1)+2]);
                DP[3*i+2] = costs[i][2] + min(DP[3*(i-1)+0], DP[3*(i-1)+1]);
            }
            
            int result = INT_MAX;
            for(i=0; i<3; i++)
                result = min(result, DP[3*(n-1)+i]);
                
            return result;
        }
    };

Log in to reply
 

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