Ускорение функции с динамическим программированием

Question

У меня есть эта программа

//h is our N
    static int g=0;
    int fun(int h){
        if(h<=0){
                  g++;
                  return g;
                  }
    return g+fun(h-1)+fun(h-4);
    }

Можно ли ускорить его с помощью динамического программирования?

Я понял, что эта функция работает в O (2 ^ n)

Я предполагаю сократить время работы с помощью динамического программирования, но не понимаю концепции.

Просто просим подтолкнуть в правильном направлении.

Answer 1

Хотя я не могу дать ответ на ваш настоящий вопрос, я заинтригован чем-то совершенно другим, а именно утверждением

return g+fun(h-1)+fun(n-4);

Очевидно, что ваша функция имеет побочный эффект изменения глобальной статической переменной g. Я не уверен на 100%, действительно ли выражение оператора return оценивается явно определенным образом или результат может быть неопределенным.

Было бы неплохо подумать о порядке, в котором выполняются эти вызовы функций, и о том, как это влияет на g и, следовательно, на результат функции.

Answer 2

Если мы определим, что порядок суммирования в g + fun (h-1) + fun (n-4) слева направо, то это хорошо определенная проблема. При этом я получаю значения для веселья (n), n = 1, ..., 15:

3, 6, 10, 15, 33, 74, 154, 295, 575, 1143, 2269, 4414, 8508, 16396, 31634

Возвращаемое значение fun (n) оценивается как последовательность суммирования с не убывающими элементами. Каждое слагаемое на единицу больше предыдущего (возвращает g ++;) или совпадает с предыдущим (return g + fun () + fun ()). Последовательность выполнения операторов возврата зависит только от входного параметра fun (). Таким образом, с g, установленным в начальное значение! = 0, мы получаем те же слагаемые, что и при g = 0, но каждое слагаемое больше для того же начального значения. При этом fun (n) с начальным g> 0 вернет значение, которое на g * количество выполненных операторов возврата больше, чем с начальным g = 0.

Определите A (n) как число выполненных операторов возврата при выполнении fun (n) и G (n) число выполненных операторов возврата в , если предложение (то же самое, что и число выполнений операторов g ++). Для A и G выполняется:

A(n) = A(n-1) + A(n-4) + 1
G(n) = G(n-1) + G(n-4)
A(n) = 1 and G(n) = 1, for n <= 0

Из этих наблюдений видно, что при n> 0 выполняется:

fun(n) = fun(n-1) + G(n-1) * A(n-4) + fun(n-4)

Простая реализация Python:

def x( h ):
  Rg = { -3:1, -2:1, -1:1, 0:1 }
  Ra = { -3:1, -2:1, -1:1, 0:1 }
  F  = { -3:1, -2:1, -1:1, 0:1 }
  for i in xrange( 1, h+1 ):
    F[i] = F[i-1] + Rg[i-1]*Ra[i-4] + F[i-4]
    print i, F[i]
    Rg[i] = Rg[i-1] + Rg[i-4]
    Ra[i] = Ra[i-1] + Ra[i-4] + 1

@ stakx: для выражения g + fun (h-1) + fun (h-4) у нас не может быть гарантии порядка оценки, особенно в C.

Answer 3

OK. Начнем с веселья (сериализованная версия, где порядок оценки навязан).

int fun(int h){
    if(h<=0){
         g++;
         return g;
    }
    int tmp1 = g;
    int tmp2 = fun(h-1);
    int tmp3 = fun(h-4);
    return tmp1+tmp2+tmp3;
}

Давайте сосредоточимся на g и забудем текущий результат функции

Теперь легко изменить функцию для передачи в g в качестве параметра и возврата в результате нового значения g.

int gun(int h, int g0){
    if(h<=0){
         return g0+1;
    }
    int tmp1 = g0;
    int tmp2 = gun(h-1, g0);
    int tmp3 = gun(h-4, tmp2);
    return tmp3;
}

What can be simplified into:

int gun(int h, int g0){
    if(h<=0){
         return g0+1;
    }
    return gun(h-4, gun(h-1, g0));
}

Теперь вернемся к веселью:

int fun2(int h, int g0){
    if(h<=0){
         return g0+1;
    }
    return g0+fun2(h-1, g0)+fun2(h-4, gun(h-1,g0));
}

fun2 делает то же самое, что и первоначальное веселье, но теперь, когда мы убрали побочный эффект и функция зависит только от его параметра, мы можем запоминать результаты (сохранять уже вычисленные результаты в массиве), что должно ускорить вычисления.

Мы все еще можем немного упростить оружие. Параметр g0 на самом деле не нужен, давайте установим его на 0.

int gun2(int h){
    if(h<=0){
         return 1;
    }
    return gun2(h-4) + gun2(h-1);
}

Мы можем даже определить fun3 с параметром g0, установленным в 0, отныне немного проще, но он все равно должен вызывать fun2. Я пока не вижу, как это упростить, но это возможно.

int fun3(int h){
    if(h<=0){
         return 1;
    }
    return fun3(h-1)+fun2(h-4, gun2(h-1));
}

Answer 4

Да, можно использовать DP, чтобы ускорить его и избежать использования стека ЦП, но я согласен со stakx относительно побочного эффекта изменения глобальной статической переменной g. Лучше предоставить математическое выражение, потому что приведенная выше рекурсивная функция может дать другой результат в зависимости от порядка и количества вызовов.