Ошибка в динамическом программировании. Что означает «Ошибка времени выполнения: код выхода -1073741571»?

Question

Мне нужна помощь в отладке моего кода для проблемы - https://codeforces.com/contest/520/problem/B

Я пытался решить эту проблему с помощью динамического программирования, но я получаю ошибку. Я хочу знать, почему я получаю ошибку во время выполнения?

Идея, которую я использовал:

1. если n становится равным m, мне больше не нужно нажимать кнопки;
2. если n становится больше, чем m, то единственный способ добраться до m - это вычитать 1 каждый раз. Таким образом (n-m) движется.
3. и для n

Ошибка, которую я получаю - Ошибка времени выполнения: код выхода -1073741571

Код, который я реализовал.

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

ll dfs(ll n, ll m){
    if(n == 0)  return INT_MAX;
    if(n == m){
        return 0;
    }
    if(n > m) {
        return abs(n-m);
    }
    return 1+min(dfs(2*n,m),dfs(n-1,m));
}

int main(){
    ll n, m;
    cin >> n >> m;
    ll ans = dfs(n ,m);
    cout << ans << endl;
    return 0;
}

Answer 1

Переход к проблеме с алгоритмом, который вызывает переполнение стека:

В какой-то момент вы позвоните dfs(n=1, m=6), что в

 return 1+min(dfs(2*n,m),dfs(n-1,m));

вызовет dfs(0, 6), который немедленно возвращается из-за n == 0 и dfs(2, 6). Это вызовет dfs(4, 6), который мы пока игнорируем, и dfs(1, 6), который возвращает состояние, в котором вы уже были. Это бесконечная рекурсия.

Возможно, вы захотите избежать нажатия синего цвета, если n==2, кроме случаев, когда m==1. Возможно, некоторая специальная обработка для n==1 также может помочь.

Answer 2

Преобразование кода выхода -1073741571 в шестнадцатеричный код (например, с использованием http://www.free -test-online.com / binary / signature_converter.html : выберите «Подписано», введите номер, нажмите «Dec2Hex» ), вы получите соответствующий код ошибки Windows C00000FD.

Согласно https://docs.microsoft.com/en-us/openspecs/windows_protocols/ms-erref/596a1078-e883-4972-9bbc-49e60bebca55, это:

0xC00000FD
STATUS_STACK_OVERFLOW
A new guard page for the stack cannot be created.

Скорее всего, переполнение стека возникает из-за слишком глубокой рекурсии: каждый рекурсивный вызов функции хранит в стеке некоторые данные (регистры, адрес возврата и т. Д.), Которые после огромного количества рекурсий слишком велики. Вот почему вы должны избегать рекурсии, где это возможно.

Решением может быть попытка переформулировать свое решение, используя итеративный подход (то есть цикл for или while.