Блог

Я делаю код 322,использую coin <= numeric_limits<int>::max() вместо coin < numeric_limits<int>::max() того, чтобы уменьшить 12 мс, но я не могу понять, почему?

решение на 64 мс:

 class Solution {
public:
    int coinChange(vector<int>amp; coins, int amount) {
        vector<int> dp(amount 1, numeric_limits<int>::max());

        dp[0] = 0;
        for(int i = 0; i <= amount;   i){
            if(dp[i] != numeric_limits<int>::max())
            for(const auto amp;coin : coins){
                if(coin <= numeric_limits<int>::max() - i amp;amp; i   coin <= amount)
                dp[i   coin] = min(dp[i   coin], dp[i]   1);
            }
        }
        return dp[amount] == numeric_limits<int>::max() ? -1 : dp[amount];
    }
};
 

решение 76ms:

 class Solution {
public:
    int coinChange(vector<int>amp; coins, int amount) {
        vector<int> dp(amount 1, numeric_limits<int>::max());

        dp[0] = 0;
        for(int i = 0; i <= amount;   i){
            if(dp[i] != numeric_limits<int>::max())
            for(const auto amp;coin : coins){
                if(coin < numeric_limits<int>::max() - i amp;amp; i   coin <= amount)
                dp[i   coin] = min(dp[i   coin], dp[i]   1);
            }
        }
        return dp[amount] == numeric_limits<int>::max() ? -1 : dp[amount];
    }
};