当我使用map<pair<int,int>,int>来存储DP状态时，通过使用记忆化增加了时间复杂度

Question

我正在解决CSES-Apple 部门问题。这是一个 dp 和差最小化问题。 我们必须将一个数组分为两个子集，其总和差最小。

我使用的是基本递归，它的工作原理是由于 n（数组大小）st 的约束。 < 21 and also because elements of array can be as big as 1e9 so overall sum has large value (i.e. < 2e10). So we cannot use dp[n][sum of array].

我已经使用了回避来解决这个问题

ll helper(vector<int> & arr,int size,ll currt_sum,ll total_sum){
    if(size==0){
        return abs(2*currt_sum- total_sum);
    }
    // PICK
    ll v1 = helper(arr,size-1,currt_sum+arr[size-1],total_sum);
    // Not Pick
    ll v2 = helper(arr,size-1,currt_sum,total_sum);
    return min(v1,v2);
}

这工作正常，但我想使用

map<pair<int,ll>,ll> memo

，将recusion state helper（size，currt_sum）的值存储在备忘录中，如

m1[{size,currt_sum}] = helper(size,currt_sum)

但它工作正常但我得到了一个TLE。

使用记忆化的代码：

ll helper(vector<int> & arr,int size,ll x,ll t,map<pair<int,ll>,ll > &m1){
    if(size==0){
        return abs(2*x-t);
    }
    if(m1.find({size,x})!=m1.end()) return m1[{size,x}];
    ll v1 = helper(arr,size-1,x+arr[size-1],t,m1);
    ll v2 = helper(arr,size-1,x,t,m1);
    return m1[{size,x}] = min(v1,v2);
}
void solve()
{
    int n;
    cin>>n;
    vector<int> v1(n);
    for (int i = 0; i < n; ++i)
    {
        cin>>v1[i];
    }
    map<pair<int,ll>,ll> m1;
    ll t = accumulate(v1.begin(), v1.end(),0LL);
    cout<<helper(v1,n,0,t,m1)<<"\n";
    return;

通过记住我获得 TLE 的回避代码，这怎么可能发生？如果有人解释这一点将会很有帮助。预先感谢。

Answer 1

你的“dp状态”不是。

动态规划通过将问题划分为一组较小的重叠子问题来解决问题。但是，您的子问题不会重叠。

您永远不会使用相同的

helper

和

size

参数组合来调用

x

。随着递归级别的上升，

size

总是下降，并且在同一级别进行的两次调用中

x

是不同的。地图永远找不到任何东西。整个算法只是一个完整的暴力搜索。地图并没有加快速度。