零钱兑换II问题中DP数组用int为何会触发溢出？

在零钱兑换II问题中，使用int类型定义DP数组会触发溢出错误，但将DP数组类型改为unsigned int后即可正常运行，以下是具体对比及原因解析：

可正常运行的代码 #

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<unsigned int > dp(amount+1, 0);
        dp[0]=1;
        for (int value: coins){
            for (int i=value; i<amount+1; ++i){
                dp[i]+=dp[i-value];
            }
        }
        return dp[amount]; 
    }
};

触发溢出错误的代码 #

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int > dp(amount+1, 0);
        dp[0]=1;
        for (int value: coins){
            for (int i=value; i<amount+1; ++i){
                dp[i]+=dp[i-value];
            }
        }
        return dp[amount]; 
    }
};

翻译后的错误信息 #

第8行第22个字符：运行时错误：有符号整数溢出：27131803 + 2123074792无法用value_type（即'int'）类型表示（solution.cpp）
摘要：UndefinedBehaviorSanitizer：未定义行为 prog_joined.cpp:17:22

溢出原因 #

• 零钱兑换II的核心是计算凑成目标金额的组合数，当目标金额较大、硬币面额较小时，组合数会急剧增长，远超int类型的取值上限。
• 标准环境下int为32位有符号整数，取值范围是-2^31到2^31-1（即-2147483648至2147483647）。错误信息中的相加结果（27131803 + 2123074792 = 2150206595）已经超过了2^31-1的上限，触发有符号整数溢出。
• unsigned int是32位无符号整数，取值范围为0到2^32-1（4294967295），能容纳更大的组合数，因此不会触发溢出问题。

内容的提问来源于stack exchange，提问作者OXEN