Программирование на Java: пример динамического программирования на лестнице

Хорошо, вот что делает код.

 `if (n<0)`
    `return 0;`

Если осталось недостаточно шагов, то не считайте их. Например, если осталось два шага, но пользователь пытается сделать три шага, то это не считается возможной комбинацией.

else if (n==0) return 1;

Если количество оставшихся шагов совпадает с количеством доступных шагов, которые пытается выполнить пользователь, это возможная комбинация. Итак, верните 1, потому что это возможная комбинация, и ее следует добавить к общему количеству допустимых комбинаций.

else if (map[n]>-1) return map[n];

Вот часть динамического программирования. Предположим, что все значения в массиве имеют значение -1. Итак, если число больше -1, оно уже решено, поэтому верните общее количество комбинаций из шага номер n вместо его разрешения.

`map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);`

return map[n]; }

Наконец, эта часть решает код. Количество возможных комбинаций равно количеству возможных комбинаций, которые пользователь может получить, если сделает 1 шаг + количество возможных комбинаций, которые пользователь может получить, если он сделает 2 шага + количество возможных комбинаций, которые пользователь может получить, если он сделает три шага.

Например, предположим, что есть 5 шагов

Простой запуск будет выглядеть так:

//The number of solutions from the fifth step

countDp(5) = countDp(4)+countDp(3)+countDp(2);

//Number of solutions from the fourth step

countDP(4) = countDp(3)+countDp(2)+countDp(1);

//Number of solutions from the third step

countDp(3) = countDp(2)+countDp(1)+countDp(0);
//Number of solutions from the second step
countDp(2) = countDp(1)+countDp(0)+countDp(-1);
//Number of solutions from the first step
countDp(1) = countDp(0) + countDp(-1)+countDp(-2);
//Finally, base case
countDp(0) = 1;

countDp(-1)= 0;
countDp(-2)= 0;
countDp(1) = 1+0+0 = 1;
countDp(2) = 1+1+0 = 2;  //Dynamic programming: did not have to resolve for countDp(1), instead looked up the value in map[1]
countDp(3) = 2+1+1 = 4;  //Dynamic programming, did not have to solve for countDp(1), countDp(2), instead looked up value in map[1] and map[2]
countDp(4) = 4+2+1=7 //Dynamic programming, did not have to solve for CountDp(3),CountDp(2), CountDp(1), just looked them up in map[3],map[2],map[1]
countDp(5)=  2+4+7=13 //Dynamic programming, just used map[4]+map[3]+map[2]

почему и как она использует карту функций здесь?

В книге показан метод динамического программирования, называемый memoization. Он используется, чтобы избежать повторного вычисления одного и того же числа: если элемент не -1, то он был вычислен снова, и его повторное вычисление означало бы потерю большого количества циклов процессора. DP вычисляет значение один раз, а затем возвращает его каждый раз, когда это значение необходимо.

карта здесь массив правильно?

Правильно, map имеет тип массива.

Я не вижу ни одной строки для сохранения ввода в массив карт, но как он что-то вернет?

Это будет задание в третьей строке снизу:

map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);

Кто-нибудь знает версию этого кода на C++ или C? Трудно понять этот код. Возможно, не из-за грамматики JAVA, а из-за неявной структуры динамического программирования.

Правильно, DP и мемоизация требуют некоторого времени, чтобы привыкнуть. Выполните этот алгоритм один раз с бумагой и карандашом для небольшого числа, скажем, 10. Это покажет вам, как оптимальная подструктура ответа помогает этому алгоритму так быстро найти ответ.

Какова будет временная сложность этого алгоритма? Оно должно быть меньше O(3^n) ?

Абсолютно! Каждый элемент вычисляется ровно один раз, и каждый элемент требует амортизированных O(1) для вычисления, поэтому общая сложность этого кода составляет O(N). Это может показаться нелогичным, поскольку вы наблюдаете, как цепочка рекурсивных вызовов для вычисления countDP(K) принимает O(K) рекурсивных вызовов. Однако каждый вызов завершает вычисление K элементов map (обратите внимание, что map — это улица с односторонним движением: как только вы установите неотрицательное значение в ячейку, оно навсегда останется неотрицательным, поэтому повторное вычисление такое же значение через любой другой путь вызова заняло бы такое же O(1) времени.

1.) map представляет собой целочисленный массив. Обозначение в Java таково, что map[n] возвращает целочисленное значение по индексу n.

2.) Возврат представляет собой целое число, поскольку map[n] возвращает целочисленное значение по индексу n. Единственный раз, когда значение сохраняется в массиве, это

map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);

Это рекурсивный вызов для нахождения суммы шагов путем подсчета всех возможных комбинаций 1, 2 и 3.

3.)

int countDP(int n, int map[])
{
if (n<0)
    return 0;
else if (n==0)
    return 1;
else if (map[n]>-1)
    return map[n];
else {
    map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);
    return map[n]; 
}


}

4.) Да, сложность будет намного быстрее, чем O(3^n).

Решение JavaScript: (итеративное)

function countPossibleWaysIterative(n) {
  if (n < 0){
    return -1; // check for negative, also might want to check if n is an integer
  } if (n === 0) {
    return 0; // for case with 0 stairs
  } else if (n === 1) {
    return 1; // for case with 1 stairs
  } else if (n === 2) {
    return 2; // for case with 2 stairs
  } else {

    var prev_prev = 1;
    var prev = 2;
    var res = 4; // for case with 3 stairs

    while (n > 3) { // all other cases
      var tmp = prev_prev + prev + res;
      prev_prev = prev;
      prev = res;
      res = tmp;
      n--;
    }
  }
  return res;
}

/**
 * Created by mona on 3/3/16.
 */
import java.util.Hashtable;
public class StairCount {
    /*
     A man is running up a staircase with n steps, and can go either 1 steps, 2 steps,
      or 3 steps at a time. count how many possible ways the child can run the stairs.
     */
    static Hashtable<Integer, Long> ht=new Hashtable<>();

    public static long stairs(int n){
        if (!ht.containsKey(1)){
            ht.put(1, (long) 1);
        }
        if (!ht.containsKey(2)){
            ht.put(2, (long) 2);
        }
        if (!ht.containsKey(3)){
            ht.put(3, (long) 4);
        }

/*
        if (!ht.containsKey(n)){
            ht.put(n, stairs(n-1)+ht.get(1)+stairs(n-2)+ht.get(2)+stairs(n-3)+ht.get(3));
        }
*/
        if (!ht.containsKey(n)){
            ht.put(n, stairs(n-1)+stairs(n-2)+stairs(n-3));
        }
        return ht.get(n);
    }
    public static void main(String[] args){
        System.out.println(stairs(4));

    }
}

// ответ для 4 - 14, а для 5 - 27. Для закомментированной строки. Может кто-нибудь прокомментировать, почему мой мыслительный процесс был неправильным?