找到所有下楼梯的路径？

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

因为如果你的位置高了一步，你唯一的选择就是下降一步，此时你就处于底部了。

从那里，很容易找到解决方案数量的递归。如果你仔细想想，你采取的任何步骤序列要么以一小步作为最后一步，要么以一大步作为最后一步。在第一种情况下，n - 1 个楼梯的每个 S(n - 1) 个解都可以通过多走一步来扩展为一个解，而在第二种情况下，n - 1 个楼梯的每个 S(n - 2) 个解都可以扩展为一个解。 - 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. 设置 S[0] = S[1] = 1
3. 对于从 2 到 n（含）的 i，设置 S[i] = S[i - 1] + S[i - 2] 。
4. 返回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。由于第二项很快就会降至零，因此您可以通过计算

(1 / √(5)) Φⁿ

并向下舍入来获得第 n 个斐波那契数。此外，您可以通过重复平方在 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

您的解决方案听起来不错。

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 4

@templatetypedef 给出了很好的答案 - 我将这个问题作为练习，并通过不同的路线得出了斐波那契数：

这个问题基本上可以简化为 二项式系数对于组合问题很方便：一次取 k 的 n 个事物的组合数（称为 n 选择 k）可以通过等式

考虑到这一点以及当前的问题，您可以暴力计算解决方案（只需进行组合计数）。 “采取 2 步”的数量必须至少为零，最多可以为 50，因此组合数量是 C(n,k) 的总和，其中 0 <= k <= 50 ( n= 的数量要做出的决定，k = 从 n 中取出的 2 的数量）

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 5

实际上，你可以证明攀登的方式数就是斐波那契数列。这里有很好的解释： http://theory.cs.uvic.ca/amof/e_fiboI.htm

Answer 6

解决问题和使用动态规划解决方案解决问题可能是两件不同的事情。

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

一般来说，要解决一个给定的问题，我们需要解决问题的不同部分（子问题），然后将子问题的解决方案组合起来得出整体解决方案。通常，许多这些子问题实际上是相同的。动态规划方法力求每个子问题只求解一次，从而减少计算量

这使我相信您想要寻找一个既递归，并使用备忘录设计模式。递归通过将问题分解为子问题来解决问题，而备忘录设计模式允许您缓存答案，从而避免重新计算。 （请注意，可能有一些缓存实现不是 Memo 设计模式，您也可以使用其中之一）。

解决：

我采取的第一步是手动解决一些问题，其中 N 的大小不同或不断增加。这将为您提供一个模式来帮助您找出解决方案。从 N = 1 开始，到 N = 5。（正如其他人所说，它可能是斐波那契数列的一种形式，但在解决和理解问题之前我会自己确定这一点）。

从那里，我会尝试制定一个使用递归的通用解决方案。递归通过将问题分解为子问题来解决问题。

从那里，我会尝试将以前的问题输入缓存到相应的输出，从而记住它，并制定涉及“动态编程”的解决方案。

即，也许您的函数之一的输入是 2, 5，正确的结果是 7。创建一些从现有列表或字典（基于输入）中查找此内容的函数。它将查找使用输入 2, 5 进行的调用。如果没有找到，则调用该函数进行计算，然后存储并返回答案（7）。如果它确实找到了，则不必费心计算它，并返回之前计算的答案。

Answer 7

这是一个非常简单的 CSharp 中这个问题的简单解决方案（我相信您可以将其移植到几乎不需要更改到 Java/C++ 的情况下）。
我增加了一点复杂性（增加了您也可以走 3 步的可能性）。如果需要，您甚至可以将此代码概括为“从 1 到 k 步”，并在添加步骤（最后一个 if 语句）中使用 while 循环。

我结合使用了动态规划和递归。使用动态规划避免了前面每一步的重新计算；减少与调用堆栈相关的空间和时间复杂度。然而，它增加了一些空间复杂度（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

使用递归可以很好地解决问题：

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);
   }
}

并在 main 中：

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

Answer 9

这是一个加权图问题。

• 从 0 到 1 只有 1 种方式 (0-1)。
• 有两种方法可以得到 2：从 0 和从 1（0-2、1-1）。
• 您可以通过三种方式得到 3：从 1 和从 2（2 有两种方式）。
• 从 2 到 3，您可以通过五种方式到达 4（2 有两种方式，3 有三种方式）。
• 你可以得到 5 种八种方法，...

递归函数应该能够处理这个问题，从 N 开始向后工作。

Answer 10

完整的 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());
        }
    }

Answer 11

迟到的基于 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));
}

Answer 12

这是一个 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 13

哟，我刚刚开始编程，没有算法设计和分析的经验。

我不确定这个解决方案（在 JS 中）的效率如何，但对我来说它似乎很简洁。

/**
 * print paths for the stair case problem with 1 and 2 step move possible
 * @param {*} stepsRemaining - number of steps remaining
 * @param {*} stepsTaken - number of steps to be taken at this move
 * @param {*} currentPath - array containing a path till this move
 * @returns
 */

const ONE_STEP_TAKEN = 1;
const TWO_STEPS_TAKEN = 2;

function printPaths(stepsRemaining, stepsTaken, currentPath = []) {
  // base cases

  // 1. wrong path, is discarded
  if (stepsRemaining < 0) { return; }

  // 2. correct path, is logged
  if (stepsRemaining === 0) {
    console.log(currentPath);
    return;
  }

  // recursive cases

  // 1. take 1 step, add move to current path, and leave calculating and
  //    logging further moves to recursion
  printPaths(stepsRemaining - 1, ONE_STEP_TAKEN, currentPath.concat(1));

  // 2. take 2 steps, add move to current path, and leave calculating and 
  //    logging all further moves to recursion
  printPaths(stepsRemaining - 2, TWO_STEPS_TAKEN, currentPath.concat(2));
}

printPaths(4);
/** logs
[ 1, 1, 1, 1 ]
[ 1, 1, 2 ]
[ 1, 2, 1 ]
[ 1, 3 ]
[ 2, 1, 1 ]
[ 2, 2 ]
[ 3, 1 ]
 */

Answer 14

可能是我错了..但应该是：

S(1) =0
S(2) =1

在这里我们正在考虑排列，所以这样

S(3) =3
S(4) =7