Dynamic Programming Using STL Vectors Makes Program Freeze Beyond Certain Values

Question

I wrote the following program, trying to optimize a recursive algorithm using Dynamic Programming.

#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";
    }
}

The base conditions for the recursive function are already specified inside the vector, and the function does work for the base conditions. It works correctly for mini(1), mini(2), ..., mini(5). Whenever I am trying anything from mini(6) or beyond, the program just freezes.

After a bit of debugging, the problem does seem to be that the function is unable to read any of the values that we are subsequently adding into the memory vector. Which is why the following works:

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.

However,

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

Here, mini(3) should have been added into the vector and used, but the function somehow doesn't seem to be able to do that.

It seems that the function is unable to perform recursions beyond a single level. I have no idea why, and would very much prefer some reason why this is happening.

Nothing changes the size of `memory`; so this line `memory[n]=m;` always indexes _"past the end"_ which is Undefined Behaviour (the previous if-test checks for in-bounds access and the above line of code is in the `else`). — Richard Critten, Jan 13 '22 at 19:02
Suggestion: Please read [Why should I **not** `#include `?](https://stackoverflow.com/Questions/31816095/Why-Should-I-Not-Include-Bits-Stdc-H.) — Ted Lyngmo, Jan 13 '22 at 19:05
you dont seem to be using `append` for vector and it is fixed size initialized. — macroland, Jan 13 '22 at 19:07
So, from what I get understand from @RichardCritten and macroland 's answers are that I can use indexing for vectors, but not beyond a fixed size beyond which I would need to use `append()`. However, using `append()` would create further problems as I would be unable to insert elements at specific positions, which is required in this program. So, I used `memory.resize()` to enlarge the vector when required. That seems to fix it. — elementalneil, Jan 14 '22 at 08:19

score 1 · Accepted Answer · answered Jan 14 '22 at 08:32

Following insights from the comments, the problem has been solved.

There were two issues with the initial program:

Trying to insert elements beyond the current size of the vector: To fix this issue, use an if statement before inserting elements to the vector to ensure that it has the correct capacity.
```
if(memory.capacity()<(n+1)){
    memory.resize(n+1);
}
memory[n]=m;
```
Using items from memory that we did not previously insert: When we are resizing memory from the previous point, we are also creating empty values at spots that we did not insert into before. For example, mini(7) would insert the values of mini(3) and mini(7) into memory. The values of mini(4), mini(5) and mini(6) would remain 0. Later when we use the function, the values of mini(4), mini(5) and mini(6) would be found in the memory to be 0, and be used as such, leading to incorrect answers.

Fixing both errors, the revised function looks like this:

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;
    }
}

Please note that a `vector` might have a [`capacity`](https://en.cppreference.com/w/cpp/container/vector/capacity) greater than its [`size`](https://en.cppreference.com/w/cpp/container/vector/size). — Bob__, Jan 14 '22 at 09:39

Dynamic Programming Using STL Vectors Makes Program Freeze Beyond Certain Values

1 Answers1