Найти все пути вниз по лестнице?

Question

Мне дали следующую проблему в интервью:

Учитывая лестницу с N ступенями, вы можете подняться на 1 или 2 ступени каждый раз.Выведите все возможные пути, идущие снизу вверх.

Например:

N = 3

Output :
1 1 1
1 2
2 1

При опросе я только что сказал использовать динамическое программирование.

S (n) = S (n-1) +1 или S (n) = S (n-1) + 2

Однако во время интервью я не очень хорошо писалхороший код для этого.Как бы вы описали решение этой проблемы?

Спасибо, действительно!

Answer 1

Я не буду писать код для вас (так как это отличное упражнение), но это классическая проблема динамического программирования.Вы на правильном пути с повторением;Это правда, что

S (0) = 1

Так как, если вы находитесь у подножия лестницы, есть только один способ сделать это.У нас также есть это

S (1) = 1

Потому что, если вы на один шаг выше, ваш единственный вариант - сделать один шаг вниз, и в этот момент вы находитесь наbottom.

Отсюда легко найти повторяемость числа решений.Если вы думаете об этом, любая последовательность шагов, которую вы делаете, заканчивается либо одним маленьким шагом в качестве последнего шага, либо одним большим шагом в качестве последнего шага.В первом случае каждое из S (n - 1) решений для n - 1 ступеней можно расширить в решение, сделав еще один шаг, а во втором случае каждое из S (n - 2) решений для n- 2 лестницы можно расширить в решение, сделав два шага.Это дает повторение

S(n) = S(n - 2) + S(n - 1)

Обратите внимание, что для оценки S (n) вам нужен только доступ к S (n - 2) и S (n - 1).Это означает, что вы могли бы решить эту проблему с помощью динамического программирования, используя следующую логику:

1. Создать массив S с n + 1 элементом в нем, проиндексированный на 0, 1, 2, ...,n.
2. Set S[0] = S[1] = 1
3. Для i от 2 до n включительно, установить S[i] = S[i - 1] + S[i - 2].
4. Return S[n].

Среда выполнения для этого алгоритма - прекрасное O (n) с использованием O (n) памяти.

Однако, возможно сделать намного лучше, чем это.В частности, давайте взглянем на первые несколько членов последовательности, которые

 S(0) = 1
 S(1) = 1
 S(2) = 2
 S(3) = 3
 S(4) = 5

Это очень похоже на последовательность Фибоначчи, и на самом деле вы можете увидеть, что

 S(0) = F(1)
 S(1) = F(2)
 S(2) = F(3)
 S(3) = F(4)
 S(4) = F(5)

Это говорит о том, что в общем случае S (n) = F (n + 1).Фактически мы можем доказать это с помощью индукции на n следующим образом.

В качестве базовых случаев мы имеем, что

S(0) = 1 = F(1) = F(0 + 1)

и

S(1) = 1 = F(2) = F(1 + 1)

Для индуктивногошаг, мы получаем это

S(n) = S(n - 2) + S(n - 1) = F(n - 1) + F(n) = F(n + 1)

И вуаля!Мы получили эту серию, написанную с точки зрения чисел Фибоначчи.Это здорово, потому что можно вычислить числа Фибоначчи в O (1) пространстве и O (LG N) времени.Есть много способов сделать это.Используется тот факт, что

F (n) = (1 / √ (5)) (Φ ⁿ + φ ⁿ )

Здесь, Φ - золотое сечение, (1 + √5) / 2 (около 1,6), а φ - 1 - Φ, около -0,6.Поскольку этот второй член очень быстро падает до нуля, вы можете получить n-е число Фибоначчи, вычислив

(1 / √ (5)) Φ ⁿ

И округливвниз.Кроме того, вы можете вычислить Φ ⁿ за O (lg n) за счет повторного возведения в квадрат.Идея состоит в том, что мы можем использовать это крутое повторение:

x ⁰ = 1

x ²ⁿ = x ⁿ * x ⁿ

x ^{2n + 1} = x * x ⁿ * x ⁿ

Вы можете показать с помощью быстрого индуктивного аргумента, что это заканчивается O (LG N) времени, что означает, что вы можете решить эту проблему, используя O (1) пространство и O (LG N) время, которое существенно лучше, чем решение DP.

Надеюсь, это поможет!

Answer 2

Вы можете обобщить свою рекурсивную функцию, чтобы она также делала уже сделанные ходы.

void steps(n, alreadyTakenSteps) {
    if (n == 0) {
        print already taken steps
    }
    if (n >= 1) {
        steps(n - 1, alreadyTakenSteps.append(1));
    }
    if (n >= 2) {
        steps(n - 2, alreadyTakenSteps.append(2));
    }
}

Это на самом деле не код, скорее псевдокод, но он должен дать вам представление.

Answer 3

Отличный ответ @templatetypedef - я выполнил эту задачу в качестве упражнения и пришел к числам Фибоначчи по другому маршруту:

Проблема может быть в основном сведена к применению Биномиальных коэффициентов , которые удобны для задач Комбинации: количество комбинаций из n вещей, взятых k за раз (называемых n, выбирают k), может быть найдено уравнение

Учитывая это и имеющуюся проблему, вы можете вычислить грубую силу решения (просто выполнив подсчет комбинации). Количество «выполнить 2 шага» должно быть не менее нуля и не более 50, поэтому количество комбинаций является суммой C (n, k) для 0 <= k <= 50 (n = количество решений для быть сделано, k = количество 2 из этих n) </p>

BigInteger combinationCount = 0;
for (int k = 0; k <= 50; k++)
{
    int n = 100 - k;
    BigInteger result = Fact(n) / (Fact(k) * Fact(n - k));
    combinationCount += result;
}

Сумма этих биномиальных коэффициентов, просто , также имеет другую формулу :

Answer 4

Ваше решение звучит правильно.

S(n):
    If n = 1 return {1}
    If n = 2 return {2, (1,1)}
    Return S(n-1)x{1} U S(n-2)x{2}

(U = Объединение , x = Декартово произведение )

Запоминание этого тривиально, и сделало бы это O(Fib(n)).

Answer 5

На самом деле, вы можете доказать, что количество способов подняться - это просто последовательность Фибоначчи. Хорошее объяснение здесь: http://theory.cs.uvic.ca/amof/e_fiboI.htm

Answer 6

проблема может быть решена с помощью рекурсии:

void printSteps(int n)
{
   char* output = new char[n+1];
   generatePath(n, output, 0);
   printf("\n");
}

void generatePath(int n, char* out, int recLvl)
{
   if (n==0)
   {
      out[recLvl] = '\0';
      printf("%s\n",out);
   }

   if(n>=1)
   {
      out[recLvl] = '1';
      generatePath(n-1,out,recLvl+1);
   }

   if(n>=2)
   {
      out[recLvl] = '2';
      generatePath(n-2,out,recLvl+1);
   }
}

и в основном:

void main()
{
    printSteps(0);
    printSteps(3);
    printSteps(4);
    return 0;       
}

Answer 7

Вот простое решение этого вопроса в очень простом CSharp (я полагаю, вы можете перенести это практически без изменений на Java / C ++). Я добавил к этому немного больше сложности (добавив, что вы также можете пройти 3 шага). Вы можете даже обобщить этот код на «от 1 до k шагов», если хотите, с помощью цикла while с добавлением шагов (последний оператор if).

Я использовал комбинацию как динамического программирования, так и рекурсии. Использование динамического программирования позволяет избежать пересчета каждого предыдущего шага; уменьшение пространственно-временной сложности, связанной со стеком вызовов. Однако это добавляет некоторую сложность пространства (O (maxSteps)), которую, я думаю, ничтожно мало по сравнению с усилением.

/// <summary>
/// Given a staircase with N steps, you can go up with 1 or 2 or 3 steps each time.
/// Output all possible way you go from bottom to top
/// </summary>
public class NStepsHop
{
    const int maxSteps = 500;  // this is arbitrary
    static long[] HistorySumSteps = new long[maxSteps];

    public static long CountWays(int n)
    {
        if (n >= 0 && HistorySumSteps[n] != 0)
        {
            return HistorySumSteps[n];
        }

        long currentSteps = 0;
        if (n < 0)
        {
            return 0;
        }
        else if (n == 0)
        {
            currentSteps = 1;
        }
        else
        {
            currentSteps = CountWays(n - 1) + 
                           CountWays(n - 2) + 
                           CountWays(n - 3);
        }

        HistorySumSteps[n] = currentSteps;
        return currentSteps;
    }
}

Вы можете назвать это следующим образом

long result;
result = NStepsHop.CountWays(0);    // result = 1
result = NStepsHop.CountWays(1);    // result = 1
result = NStepsHop.CountWays(5);    // result = 13
result = NStepsHop.CountWays(10);   // result = 274
result = NStepsHop.CountWays(25);   // result = 2555757

Можно утверждать, что в начальном случае, когда n = 0, он мог 0, а не 1. Я решил пойти на 1, однако изменение этого предположения тривиально.

Answer 8

Решение проблемы и ее решение с использованием динамического программного решения - это, возможно, две разные вещи.

http://en.wikipedia.org/wiki/Dynamic_programming

В общем, для решения данной проблемы нам нужночтобы решить различные части проблемы (подзадачи), затем объединить решения подзадач для достижения общего решения.Часто многие из этих подзадач действительно одинаковы.Подход динамического программирования стремится решить каждую подзадачу только один раз, таким образом уменьшая количество вычислений

Это заставляет меня думать, что вы хотите найти решение, которое одновременно является Рекурсивным ,и использует Шаблон дизайна памятки .Рекурсия решает проблему, разбивая ее на подзадачи, а шаблон Memo-дизайна позволяет вам кэшировать ответы, что позволяет избежать повторного расчета.(Обратите внимание, что, возможно, есть реализации кэша, которые не являются шаблоном разработки Memo, и вы также можете использовать один из них).

Решение :

Первыйшаг, который я бы предпринял, состоял бы в том, чтобы решить некоторые проблемы вручную, с переменным или увеличивающимся размером N. Это даст вам образец, который поможет вам найти решение.Начните с N = 1, через N = 5. (как уже говорили другие, это может быть форма последовательности fibbonacci, но я бы сам определился с этим, прежде чем называть проблему решенной и понятой).

Оттам я попытался бы сделать обобщенное решение, использующее рекурсию.Рекурсия решает проблему, разбивая ее на подзадачи.

Оттуда я бы попытался создать кэш предыдущих входных данных проблемы для соответствующего вывода, следовательно, запомнив его и приняв решение, включающее «Динамическое программирование».Msgstr ""

Т.е., возможно, входные данные для одной из ваших функций 2, 5, и правильный результат был 7.Сделайте некоторую функцию, которая ищет это из существующего списка или словаря (на основе ввода).Он будет искать вызов, который был сделан со входами 2, 5.Если он не находит его, вызовите функцию для его вычисления, затем сохраните и верните ответ (7).Если он найдет его, не пытайтесь рассчитать его и верните ранее рассчитанный ответ.

Answer 9

Вот решение C ++. Это печатает все возможные пути для данного количества лестниц.

// Utility function to print a Vector of Vectors
void printVecOfVec(vector< vector<unsigned int> > vecOfVec)
{
    for (unsigned int i = 0; i < vecOfVec.size(); i++)
    {
        for (unsigned int j = 0; j < vecOfVec[i].size(); j++)
        {
            cout << vecOfVec[i][j] << " ";
        }
        cout <<  endl;
    }
    cout << endl;
}

// Given a source vector and a number, it appends the number to each source vectors
// and puts the final values in the destination vector
void appendElementToVector(vector< vector <unsigned int> > src,
                           unsigned int num,
                           vector< vector <unsigned int> > &dest)
{
    for (int i = 0; i < src.size(); i++)
    {
        src[i].push_back(num);
        dest.push_back(src[i]);
    }
}

// Ladder Problem
void ladderDynamic(int number)
{
    vector< vector<unsigned int> > vecNminusTwo = {{}};
    vector< vector<unsigned int> > vecNminusOne = {{1}};
    vector< vector<unsigned int> > vecResult;

    for (int i = 2; i <= number; i++)
    {
        // Empty the result vector to hold fresh set
        vecResult.clear();

        // Append '2' to all N-2 ladder positions
        appendElementToVector(vecNminusTwo, 2, vecResult);

        // Append '1' to all N-1 ladder positions
        appendElementToVector(vecNminusOne, 1, vecResult);

        vecNminusTwo = vecNminusOne;
        vecNminusOne = vecResult;
    }

    printVecOfVec(vecResult);
}

int main()
{
    ladderDynamic(6);
    return 0;
}

Answer 10

Поздний ответ на основе С

#include <stdio.h>
#include <stdlib.h>
#define steps 60
static long long unsigned int MAP[steps + 1] = {1 , 1 , 2 , 0,};

static long long unsigned int countPossibilities(unsigned int n) {
    if (!MAP[n]) {
       MAP[n] = countPossibilities(n-1) + countPossibilities(n-2);
    }
    return MAP[n];
}

int main() {
   printf("%llu",countPossibilities(steps));
}