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

Question

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

код дается как ниже

public static 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]; } 
} 

Я знаю, C и C++, не JAVA. Это из книги интервью «Крекинг-кодирование». Может кто-нибудь может объяснить

1. , как и почему она использует функцию карты здесь? карта здесь массив справа?

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

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

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

Буду признателен.

Спасибо, ребята

Answer 1

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

`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] 

Answer 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).

Answer 3

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^п).

Answer 4

решение 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; 
} 

Answer 5

/** 
* 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. Для строки, которая прокомментирована. Может кто-нибудь прокомментировать, почему мой мыслительный процесс был неправильным?