I am calculating the least amounts of 3s and 5s that sum up to N. I used memoization and recursive algorithm.

The problem is, when I run the program and input 11, temp3 = calculate(8) returns 1, when it should clearly return 2.

I have checked that before calculate(8) is called, arr[8] = 2 already.

#include <iostream>

using namespace std;

int init, N, temp3, temp5;
int arr[5001];

int calculate(int N) {
    
    if(arr[N]==0){
        temp3 = calculate(N-3);
        temp5 = calculate(N-5);
        if (temp3!=-1 && temp5!=-1){
            if (temp3<=temp5) {
                arr[N] = temp3   1;
            }
            else {
                arr[N] = temp5   1;
            }
        }
        else if (temp5!=-1) {
            arr[N] = temp5   1;
        }
        else if (temp3 != -1) {
            arr[N] = temp3   1;
        }
        else {
            arr[N] = -1;
        }
    }
    return arr[N];
}

int main()
{
    arr[1]=-1;arr[2]=-1;arr[3]=1;arr[4]=-1;arr[5]=1;
    cin >> init;
    cout << calculate(init);
    return 0;
}

CodePudding user response：

You are operating on global variables! Several recursive calls use the same variables and it happens that the call temp5 = calculate(N-5); overwrites the temp3 value that has previously been set by the call temp3 = calculate(N-3);!

Solution: Do not use global variables!

int temp3 = calculate(N-3);
int temp5 = calculate(N-5);

This way every recursive call has its own set of variables and won't overwrite the values stored in another recursive call.

Generally: Consider always if you really, really need a global variable at all. While sometimes they cannot be avoided (without unreasonable effort) they usually are only a source of evil!