利用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)应该被添加到向量中并使用，但是函数似乎无法做到这一点。

该函数似乎无法在单个级别之外执行递归。我不知道为什么，也很想知道为什么会发生这种情况。

Answer 1

根据评论的见解，这个问题已经解决了。

最初的方案有两个问题：

1. Trying以插入向量当前大小以外的元素:要解决此问题，请在向向量插入元素之前使用if语句，以确保其具有正确的容量。if(memory.capacity()<(n+1)){ memory.resize(n+1)；} memoryn=m;

以前没有插入

1. Using的内存中的项:当我们从前一点调整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;
    }
}