C++ DP solution 36ms


  • 0
    J

    Time complexity is O(nkk), space complexity is O(k)

    class Solution {
    public:
        int getMin(vector<int> &dp, int k){
            int result=INT_MAX;
            for(int i=0;i<dp.size();++i)
                if(i!=k && result>dp[i])result=dp[i];
            return result;
        }
        int minCostII(vector<vector<int>>& costs) {
            int n=costs.size();
            if(n==0)return 0;
            int k=costs[0].size();
            vector<vector<int>>dp(2,vector<int>(k,0));
            for(int i=0;i<k;++i)dp[0][i]=costs[0][i];
            for(int row=1;row<n;++row)
                for(int col=0;col<k;++col)
                    dp[row%2][col]=costs[row][col]+getMin(dp[(row-1)%2],col);
            return getMin(dp[(n-1)%2],-1);
        }
    };

Log in to reply
 

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