LeetCode 322.零钱兑换代码出现无符号偏移量加法溢出运行时错误

本地VS Code中代码可正常运行，但在LeetCode平台使用测试用例coins = [1,2,5]、amount = 11时，出现如下运行时错误：

Line 1117: Char 34: runtime error: addition of unsigned offset to 0x504000000110 overflowed to 0x50400000010c (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/13/../../../../include/c++/13/bits/stl_vector.h:1126:34

出错代码 #

int coinChange(vector<int>& coins, int amount) {
   int n = coins.size();
   vector<vector<int>> dp(n+1,vector<int>(amount+1,999));

   for(int i=0;i<n+1;i++)
      dp[i][0] = 0;
   for(int i=0;i<amount+1;i++){ 
      dp[0][i] = 999;
   }

   for(int i=1;i<n+1;i++){
      for(int j=1;j<amount+1;j++){
            if(coins[i-1]<=amount)
               dp[i][j] = min( dp[i][j-coins[i-1]]+1, dp[i-1][j] );
            else
               dp[i][j] = dp[i-1][j];
      }
   }

   if(dp[n][amount]>=999) return -1;
   return dp[n][amount];
}

错误原因 #

数组越界访问：代码中的判断条件if(coins[i-1]<=amount)逻辑错误，应该判断当前硬币面值是否小于等于当前处理的金额j，而非总金额amount。当coins[i-1] > j时，j - coins[i-1]会变成负数，vector的索引是无符号类型，负数会被转换为超大的无符号值，导致访问超出数组范围的内存，触发溢出错误。

另外初始化时dp[0][i] = 999的设置不够严谨，若amount大于999，会导致后续判断失效，建议用amount + 1作为不可达的标记值（因为最多需要amount个1元硬币，超过这个数就代表无法凑出该金额）。

修复后的代码 #

int coinChange(vector<int>& coins, int amount) {
    int n = coins.size();
    // 用amount+1作为不可达标记，避免999不够大的情况
    vector<vector<int>> dp(n + 1, vector<int>(amount + 1, amount + 1));

    // 金额为0时，所需硬币数为0
    for (int i = 0; i < n + 1; i++)
        dp[i][0] = 0;

    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < amount + 1; j++) {
            // 判断当前硬币是否能用于凑金额j
            if (coins[i-1] <= j) {
                dp[i][j] = min(dp[i][j - coins[i-1]] + 1, dp[i-1][j]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    // 若结果大于等于amount+1，说明无法凑出该金额
    return dp[n][amount] >= amount + 1 ? -1 : dp[n][amount];
}

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