在20楼爬上n楼梯的可能性

Question

我解决了一个递归问题,其中函数int stairs(int n)返回爬楼梯到n的可能性的数量,条件是采取1步或2步.以下代码解决了这个问题:

int stairs(int n)
{
   if (n<0) return 0;
   if (n==0) return 1;
   return stairs(n-1) + stairs(n-2);
}

现在我有一个约束条件:如果你到了20楼,你必须使用一台自动将你带到第n层的电梯.如果由于某种原因你跳过20级(例如,达到19级然后爬2层到21级),继续照常.找出上述约束的可能性数量.到目前为止我所做的是:

int stairs20(int n)
{
    if (n<=20) return stairs(n);
    return stairs(20) + stairs(n-21);
}

代码背后的逻辑是计算到达20楼的可能性的数量,以及21楼及以上的可能性的数量.我认为这不能找回正确的答案,并希望了解我的错误在哪里或我不算什么？

Answer 1

当n>20,

• 你可以先到达20楼,然后一路向上走=> stairs(20)

• 你也可以到达19楼,然后从21楼到21楼,你有stairs(n-21)办法去楼层,所以=>stairs(19)*stairs(n-21)

所以总结一下stairs(20) + stairs(19) * stairs(n-21).

您可以使用动态编程来避免计算相同的值.