Is there a bug in this judge ?


  • 0
    Y

    I use a DP method to solve this problem. ref : http://blog.csdn.net/gao1440156051/article/details/52263742
    First I wrote like this :

    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            int len=coins.size();
            if (amount<0) return -1;
            vector<int> dp(amount+1,INT_MAX);
            dp[0]=0;
            for(int i=1;i<=amount;i++){  //i stands for sum to make up
                for(int j=0;j<len;j++){  //j stands for the index of coins
                    if(dp[i-coins[j]]!=INT_MAX && i>=coins[j]){
                        dp[i]=min(dp[i],dp[i-coins[j]]+1);
                    }
                }
            }
            return dp[amount]==INT_MAX?-1:dp[amount]; 
        }
    };
    

    And there was a error " Runtime Error " . I checked with other solutions and compared, then I only rewrite the order in the if condition from if(dp[i-coins[j]]!=INT_MAX && i>=coins[j]) to if(i>=coins[j] && dp[i-coins[j]]!=INT_MAX). In theory, there should not be any differences, however, it is accepted this time.

    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            int len=coins.size();
            if (amount<0) return -1;
            vector<int> dp(amount+1,INT_MAX);
            dp[0]=0;
            for(int i=1;i<=amount;i++){  //i stands for sum to make up
                for(int j=0;j<len;j++){  //j stands for the index of coins
                    if(i>=coins[j] && dp[i-coins[j]]!=INT_MAX){
                        dp[i]=min(dp[i],dp[i-coins[j]]+1);
                    }
                }
            }
            return dp[amount]==INT_MAX?-1:dp[amount];   
        }
    };
    

Log in to reply
 

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