A C++ solution of beginner (includes general idea of DP problems)


  • 0

    I'm also a beginner.
    In my idea, when come to DP problems (such as find the most 'optimum' solution), the first step is to decide use what to make a matrix/column (the element of matrix/column record the 'optimum' step). In this problem, the column is [0, 1, 2,..., amount]. Here we call the column as dp[], it has amount +1 elements.
    The second step is to find the relationship among them. In this problem, 'optimum' step of current amount dp[cur] equals to the minimum of dp[cur - 'denominations'] + 1.

    int coinChange(vector<int>& co, int am) 
    {
            if (!am)
                return 0;
    	if (co.empty())
    	    return -1;
    	int sz = co.size();
    	vector<int> dp(am + 1, -1);//initialize the dp[] as -1.
    	for (auto x : co)
    	{
    	    if (x <= am) 
    		dp[x] = 1;//set the dp[denomination] equals to 1, because we can use one coin to get the amount of each denomination.
    	}
    	for (int i = 1; i <= am; ++i)
    	{
    	    if (1 == dp[i])//skip the dp[] of each denomination.
    		continue;
    	    int minsp = INT_MAX;
    	    for (int j = 0; j < sz; ++j)
    	    {
    	        int t = co[j];
    		if (i - t > 0 && dp[i - t] > 0 && dp[i - t] < minsp)
    		    minsp = dp[i - t];
    	    }
    	    if (minsp != INT_MAX)
    		dp[i] = minsp + 1;
    	}
    	return dp[am];
    }
    

Log in to reply
 

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