Dynamic Programming Using STL Vectors Makes Program Freeze Beyond Certain Values

  c++, dynamic-programming, vector

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.

Source: Windows Questions C++

LEAVE A COMMENT