Easy understand C++ using DP


  • 2
    T
    class Solution {
    public:
        int minCost(vector<vector<int>>& costs, int row, int idx)
        {
            int costMin = INT_MAX;
            for(int i=0; i<costs[row].size(); i++)
            {
                if(i != idx)
                {
                    costMin = min(costMin, costs[row][i]);
                }
            }
            return costMin;
        }
    
        int minCostII(vector<vector<int>>& costs) {
            
            //special case
            if(costs.empty())
            {
                return  0;
            }
            
            if(costs.size() == 1)
            {
                return minCost(costs, 0, -1);
            }
            
            for(int i=1; i<costs.size(); i++)
            {
                for(int j=0; j<costs[0].size(); j++)
                {
                    costs[i][j] += minCost(costs, i-1, j);
                }
            }
            return minCost(costs, costs.size()-1, -1);
        }
    };

Log in to reply
 

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