LeetCode #377的C++ DP解法，这段代码有bug吗？

Question

此 C++ 解决方案是对 top voted Java solution 的直接翻译在讨论区。我自己的 G++ 编译器可以很好地编译和运行这个测试用例，但是 LeetCode 提交会产生错误(请快速尝试)。

我认为内存已正确初始化并且边界检查已到位。可能是什么问题？

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 1; i < dp.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i - nums[j] >= 0) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
};

int main(int argc, char** argv) {
    vector<int> nums {
        3, 33, 333,
    };
    cout << Solution().combinationSum4(nums, 10000) << endl;
    return 0;
}

测试用例:

[3,33,333]
10000

错误信息:

Line 9: Char 17: runtime error: signed integer overflow: 357856184 + 1941940377 cannot be represented in type 'int' (solution.cpp)

Answer 1

消息清楚地显示了错误。 357856184 + 1941940377 = 2299796561 大于 32 位 int 最大值 -> 2^31 - 1 = 2147483647。

在 C++ 标准中，不能保证 int 的大小。因此，为了安全起见，您可以根据 C++ 11 使用 int64_t。

https://en.cppreference.com/w/cpp/language/types