使用 STL 向量的动态编程使程序冻结超过特定值

Question

我编写了以下程序，试图使用动态规划优化递归算法。

#include <bits/stdc++.h>

using namespace std;

int mini(int n, vector<int> &memory){
    if(n<memory.size()){
        return memory[n];
    }
    else{
        int m = (n+1)+mini(((n-1)/2), memory)+mini(((n-1)-((n-1)/2)), memory);
        memory[n]=m;
        return m;
    }
}

int main(){
    vector<int> memory={0, 2, 5};

    int t;
    cin >> t;

    while(t--){
        int n;
        cin >> n;

        cout << mini(n, memory) << "\n";
    }
}

向量中已经指定了递归函数的基本条件，并且该函数确实适用于基本条件。它适用于 mini(1)、mini(2)、...、mini(5)。每当我尝试 mini(6) 或更高版本的任何东西时，程序就会冻结。

经过一些调试后，问题似乎是该函数无法读取我们随后添加到 memory 向量中的任何值。这就是以下工作的原因：

mini(5) = 6 + mini(2) + mini(2) //mini(2) is pre-specified in memory vector.
mini(4) = 5 + mini(1) + mini(2) //mini(1) and mini(2) are pre-specified.

然而，

mini(6) = 7 + mini(2) + mini(3) //mini(3) is not pre-specified into vector memory.

在这里，应该将 mini(3) 添加到 vector 中并使用，但该函数似乎无法做到这一点。

该函数似乎无法执行超出单个级别的递归。我不知道为什么，并且非常希望找到发生这种情况的原因。

Answer 1

根据评论的见解，问题已解决。

初始程序有两个问题：

尝试插入超出矢量当前大小的元素：要解决此问题，请在向矢量插入元素之前使用 if 语句以确保它有正确的容量。
```
if(memory.capacity()<(n+1)){
    memory.resize(n+1);
}
memory[n]=m;
```
使用我们之前没有插入的内存项目：当我们从上一点调整大小时 memory，我们也在我们需要的地方创建空值之前没有插入。例如，mini(7) 会将 mini(3) 和 mini(7) 的值插入到 memory 中。 mini(4)、mini(5) 和 mini(6) 的值将保持 0。后面我们使用该函数时，会在内存中发现mini(4)、mini(5)和mini(6)的值是0，并照此使用，导致错误答案。

修复这两个错误，修改后的函数如下所示：

int mini(int n, vector<int> &memory){
    if(n<memory.size() && memory[n]!=0){
        return memory[n];
    }
    else{
        int m = (n+1)+mini(((n-1)/2), memory)+mini(((n-1)-((n-1)/2)), memory);

        if(memory.capacity()<(n+1)){
            memory.resize(n+1);
        }
        memory[n]=m;
        return m;
    }
}

使用 STL 向量的动态编程使程序冻结超过特定值

Dynamic Programming Using STL Vectors Makes Program Freeze Beyond Certain Values

c++

vector

dynamic-programming