Неправильное решение, если в рекурсии добавлена ​​памятка

Question

Я создал программу DP, но проблема в том, что я получаю правильные ответы, когда не использую памятку. Как только я ввожу памятку, я начинаю получать неправильные ответы на некоторые проблемы

Вот код на C ++ 14 с отключенным запоминанием (комментируя)

#include <iostream>
#include <math.h>
#include<algorithm>

using namespace std;
int max_Number_of_turns;
int dp[9999][1000];
int changeTheDigit(int n, int d) {
    int rem = n % (int) (pow(10, 4 - d));
    n /= (pow(10, 4 - d));
    int x = n % 10;
    n /= 10;
    if (x == 9) x = 0;
    else x = x + 1;
    n = n * (10) + x;
    n = n * (pow(10, 4 - d)) + rem;
    return n;
}

int minMax(int n, int t) {
    int ans =0;
    //if(dp[n][t]>=0) { return dp[n][t];}
    if (t > max_Number_of_turns) return n;

    int N;
    for (int i = 0; i < 4; i++) {
        N = changeTheDigit(n, i + 1);
        if (t % 2 == 0) {
            //Manish chance
            if(ans==0) ans=minMax(N, t+1);
            else ans = min(ans, minMax(N, t + 1));
        } else {
            //Nitish Chance
            ans = max(ans, minMax(N, t + 1));
        }
    }
    //cout << ans << endl;
    dp[n][t]=ans;
    return ans;
}

using namespace std;

int main() {
    int T, N, M;
    cin >> T;
    while (T--) {
        cin >> N >> M;
        max_Number_of_turns=M;
        for(int i=0;i<9999;i++)
            for(int j=0;j<1000;j++)
                dp[i][j]=-1;
        if(minMax(N,1)>N){
            cout << "Nitish" << endl;
        }
        else{
            cout << "Manish" << endl;
        }
    }
    return 0;
}

Включить комментарий для заметок (то есть удалить комментарии из этой строки)

if(dp[n][t]>=0) { return dp[n][t];}

и мой код даст неправильные ответы на некоторые проблемы Например, давайте рассмотрим ввод

1
4569 12

Оригинальное правильное решение - Маниш Но если я включу памятку, мое решение будет Nitish

Можете ли вы подсказать мне, что я здесь делаю не так

Кроме того, интересным фактом является то, что если изменить код DP с

if(dp[n][t]>=0) { return dp[n][t];}

до

if(dp[n][t]>0) { return dp[n][t];}

Тогда все хорошо

Answer 1

Ваша проблема в том, что значения для n и / или t не проверяются, и поэтому могут вызывать проблемы с массивом вне границ. Это можно увидеть, если вставить в начале функции minMax следующее:

if (n < 0 || n >= 9999) cout << "n invalid at " << n << '\n';
if (t < 0 || t >= 1000) cout << "t invalid at " << t << '\n';

Выполнение этого с вашим вводом сэмпла выдает предупреждения перед выводом результата:

n invalid at 9999
n invalid at 9999
n invalid at 9999

Чтобы исправить это, вы можете просто убедиться, что вы используете памятку только тогда, когда у вас достаточно места для нее, сначала, когда проверяет значение:

if (n >= 0 && n < 9999 && t >= 0 && t < 1000 && dp[n][t] >= 0)
    return dp[n][t];

и, во-вторых, при сохранении значение:

if (n >= 0 && n < 9999 && t >= 0 && t < 1000)
    dp[n][t] = ans;