时间戳

首页 > 解决方案 > 递归函数有效，但无法记忆

c++ - 递归函数有效，但无法记忆

问题描述

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

给定一个非负整数列表 a1、a2、...、an 和一个目标 S。现在您有 2 个符号 + 和 -。对于每个整数，您应该从 + 和 - 中选择一个作为其新符号。找出有多少种分配符号的方法以使整数之和等于目标 S。对于输入[1, 1, 1, 1, 1]和 S= 3，输出应该是5。

约束是：

给定数组的长度为正且不超过 20。
给定数组中元素的总和不超过 1000。
保证您的输出答案适合 32 位整数。

我想出了以下代码：

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.) 上运行良好，但显然超过了时间限制。现在，在上面的记忆中，我得到一个运行时错误：

运行时错误：将无符号偏移添加到 0x621000008d00 溢出到 0x621000008cfc (stl_vector.h) 摘要：UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../ ../../include/c++/8/bits/stl_vector.h:933:34

我做错了什么？

标签： c++algorithmrecursiondynamic-programmingmemoization

解决方案

可以使用动态规划优化问题，将Current Index和Sum作为状态。

您的解决方案的问题在于，它Sum本身可能是一个非常大的数字或负数，并且访问如此大的索引会导致运行时错误，因为在此类平台（沙盒环境）上为您提供了有限的内存。最好的方法，是使用地图。

查看以下已接受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);

    }
};

推荐阅读