[How to from Error to AC]thoughts and extensions with C++ implementation


  • 0

    Maybe this problem seems really easy, but I make some common previous mistakes I made previously.

    Here I summary them like this:

      1.  the initialization should considered clearly. You should set different start value based 
           
          on the problem Def.
    
      2.  The different Initialization strategy  may requires us to use different Return Code 
    
      3.  IF initialized all as INT_MAX or the INT_MIN, we should be careful about any possible operation 
    
           leading to the OVERFLOW ERROR to flip the INT_MAX to -1 OR other cases.
    

    All in all , we should make it right for all the corner cases and then the recursive equation.

       class Solution {
        public:
            int coinChange(vector<int>& coins, int amount) {
                if(amount==0)  return 0;
                vector<int> dp(amount+1, amount+1);
                /*** 
                 *   dp[i]=min{dp[i-coins[k]]+1}   loop coins[k] in coins
                 **/
                dp[0]=0;
                for(int i=0; i<=amount; i++){
                    for(int val:coins){
                        if(val<=i){
                            dp[i]=min(dp[i], dp[i-val]+1);
                        }
                    }
                }
                return dp[amount]==(amount+1) ? -1:dp[amount];
            }
        };

  • 0
    2

    The key to the solution is that ....

        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;

Log in to reply
 

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