c++ - 递归函数有效，但无法内存

Question

我正在解决 LeetCode.com 上的这个动态编程问题:https://leetcode.com/problems/target-sum/

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. For input [1, 1, 1, 1, 1] and S=3, output should be 5.

约束是:

The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

我想出了以下代码:

class Solution {
public:
    vector<int> n;
    int s;
    
    int helper(vector<vector<int>>& dp, int sum, int startIndex) {
        if(startIndex==n.size()) {
            if(sum==s) return dp[startIndex][sum]=1;
            else return dp[startIndex][sum]=0;
        }
        if(dp[startIndex][sum]!=-1) return dp[startIndex][sum];
        
        
        return dp[startIndex][sum]=helper(dp, sum+n[startIndex], startIndex+1) +
               helper(dp, sum-n[startIndex], startIndex+1);
    }
    
    int findTargetSumWays(vector<int>& nums, int S) {
        n=nums;
        s=S;
        vector<vector<int>> dp(21, vector<int>(1001,-1));
        
        return helper(dp, 0, 0);
    }
};

不使用 dp 进行内存表中，代码在所有 139 个测试用例 (139 / 139 test cases passed, but took too long.) 上运行良好，但显然超过了时间限制。现在，在上面的内存中，我得到一个运行时错误:

runtime error: addition of unsigned offset to 0x621000008d00 overflowed to 0x621000008cfc (stl_vector.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_vector.h:933:34

我做错了什么？

Answer 1

该问题可以使用动态规划进行优化，具有 Current Index和 Sum作为国家。
您的解决方案的问题是 Sum单独可以是一个非常大的数字或负数，并且访问如此大的索引会导致运行时错误，因为在此类平台(沙盒环境)上为您提供有限的内存。最好的方法，是使用 map 。
查看以下具有 的解决方案接受 对 Leetcode 的判断:

typedef long long int LL;

class Solution {
public:

    std::map<pair<LL, LL>, LL> mp;

    LL find(int currentIndex, int len, LL S, std::vector<int>& nums){


        if(mp.find(make_pair(currentIndex, S)) != mp.end()){
            return mp[make_pair(currentIndex, S)];
        }

        if(S!=0 and currentIndex >= len){
            return 0;
        }


        if(S==0 && currentIndex==len){
            return 1;
        }


        LL ans = find(currentIndex+1, len, S-nums[currentIndex], nums) + find(currentIndex+1, len, S+nums[currentIndex], nums);

        mp[make_pair(currentIndex, S)] = ans;

        return mp[make_pair(currentIndex, S)];

    }

    int findTargetSumWays(vector<int>& nums, int S) {


        return find(0, nums.size(), S, nums);

    }
};