В интервью мне была задана следующая проблема:
Учитывая лестницу с 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
Однако во время интервью я не написал для этого очень хороший код. Как бы вы определили решение этой проблемы?
Спасибо, действительно!
Вы можете обобщить свою рекурсивную функцию, чтобы выполнить уже сделанные ходы.
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));
}
}
Это не действительно код, а скорее псевдокод, но он должен дать вам идею.
Я не буду писать код для вас (поскольку это отличное упражнение), но это классическая проблема динамического программирования. Вы на правильном пути с повторением; верно, что
S (0) = 1
Так как, если вы на дне лестницы, есть один способ сделать это. Мы также имеем, что
S (1) = 1
Потому что, если вы на один шаг выше, ваш единственный вариант - сделать один шаг вниз, после чего вы находитесь внизу.
Отсюда легко найти повторение числа решений. Если вы думаете об этом, любая последовательность шагов, которые вы делаете, заканчивается тем, что вы делаете один маленький шаг в качестве своего последнего шага или одного большого шага в качестве своего последнего шага. В первом случае каждое из 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). Это означает, что вы можете решить это с помощью динамического программирования, используя следующую логику:
S с n + 1 элементами в нем, индексированными на 0, 1, 2,..., n.S[0] = S[1] = 1S[i] = S[i - 1] + S[i - 2].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/& radic; (5)) (& Phi; n + & phi; n)
Здесь & Phi; представляет собой золотое отношение, (1 + & radic; 5)/2 (около 1,6) и & phis; 1 - & Phi;, около -0,6. Поскольку этот второй член быстро падает до нуля, вы можете получить n-й номер Фибоначчи, вычислив
(1/& radic; (5)) & Phi; n
И округление. Более того, вы можете вычислить & Phi; n в O (lg n) раз, повторив квадрат. Идея состоит в том, что мы можем использовать эту прохладную рекурсию:
x 0= 1
x 2n= x n * x n
x 2n + 1= x * x n * x n
Вы можете показать, используя быстрый индуктивный аргумент, что это заканчивается в O (lg n) времени, что означает, что вы можете решить эту проблему, используя O (1) пространство и время O (lg n), что существенно лучше, чем DP.
Надеюсь, это поможет!
Ваше решение звучит правильно.
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 является Union, x является Декартовым продуктом)
Запоминание это тривиально и сделает его O(Fib(n)).
Отличный ответ by @templatetypedef - я сделал эту проблему как упражнение и прибыл на номера Фибоначчи по другому маршруту:
Проблема в основном сводится к применению биномиальных коэффициентов, которые удобны для проблем сочетания: количество комбинаций n вещей, принятых k в момент времени (называемый n выбираем k) можно найти по уравнению
Учитывая это и проблему, вы можете вычислить решение грубой силы (просто счет комбинации). Число "принимать 2 шага" должно быть не меньше нуля и может составлять не более 50, поэтому количество комбинаций представляет собой сумму C (n, k) для 0 <= k <= 50 (n = число решения, k = число из 2 взятых из них n)
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;
}
Сумма этих биномиальных коэффициентов просто также имеет другую формулу:
Собственно, вы можете доказать, что количество способов набора высоты - это всего лишь последовательность фибоначчи. Хорошее объяснение здесь: http://theory.cs.uvic.ca/amof/e_fiboI.htm
Решение проблемы и ее решение с помощью решения динамического программирования потенциально могут быть разными.
http://en.wikipedia.org/wiki/Dynamic_programming
В общем, для решения данной проблемы нам необходимо решить разные части проблемы (подзадачи), а затем объединить решения подзадач для достижения общего решения. Часто многие из этих подзадач на самом деле одинаковы. Метод динамического программирования направлен на решение каждой подзадачи только один раз, что уменьшает количество вычислений
Это заставляет меня думать, что вы хотите найти решение, которое Рекурсивное, и использует шаблон оформления памятки. Рекурсия решает проблему, разбивая ее на под-проблемы, и шаблон шаблона Memo позволяет вам кэшировать ответы, тем самым избегая повторного расчета. (Обратите внимание, что, вероятно, существуют реализации кэша, которые не являются шаблоном проектирования Memo, и вы также можете использовать один из них).
Решение:
Первым шагом, который я хотел бы предпринять, было бы решить некоторые проблемы вручную, с различными или увеличивающимися размерами N. Это даст вам образец, который поможет вам разобраться в решении. Начните с N = 1, через N = 5. (как утверждают другие, это может быть форма последовательности фибоначчи, но я бы определил это для себя, прежде чем называть проблему, которая была решена и понята).
Оттуда я попытаюсь сделать обобщенное решение, в котором используется рекурсия. Рекурсия решает проблему, разбивая ее на под-проблемы.
Оттуда я попытаюсь сделать кэш предыдущих входных данных проблемы к соответствующему выводу, следовательно, memoizing его и сделать решение, которое включало "Динамическое программирование".
I.e., возможно, входы одной из ваших функций 2, 5, и правильный результат был 7. Сделайте некоторую функцию, которая будет выглядеть из существующего списка или словаря (на основе ввода). Он будет искать вызов, который был сделан с входами 2, 5. Если он не находит его, вызовите функцию для его вычисления, затем сохраните и верните ответ (7). Если он найдет его, не утруждайте его вычислением и верните ранее вычисленный ответ.
Вот простое решение этого вопроса в очень простой CSharp (я считаю, что вы можете перенести это без каких-либо изменений в Java/С++). Я добавил немного сложнее (добавив, что вы также можете пройти 3 шага). Вы можете даже обобщить этот код на "от 1 до k-шагов", если это необходимо, с циклом while при добавлении шагов (инструкция last 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, однако изменение этого предположения тривиально.
проблему можно решить довольно хорошо, используя рекурсию:
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;
}
Это проблема взвешенного графа.
Рекурсивная функция должна иметь возможность справиться с этим, работая назад от N.
Завершить код C-Sharp для этого
void PrintAllWays(int n, string str)
{
string str1 = str;
StringBuilder sb = new StringBuilder(str1);
if (n == 0)
{
Console.WriteLine(str1);
return;
}
if (n >= 1)
{
sb = new StringBuilder(str1);
PrintAllWays(n - 1, sb.Append("1").ToString());
}
if (n >= 2)
{
sb = new StringBuilder(str1);
PrintAllWays(n - 2, sb.Append("2").ToString());
}
}
Ответ на поздний C
#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));
}
Вот С++-решение. Это печатает все возможные пути для определенного количества лестниц.
// 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;
}
Возможно, я ошибаюсь.. но это должно быть:
S(1) =0
S(2) =1
Здесь мы рассматриваем перестановки так, чтобы таким образом
S(3) =3
S(4) =7