动态编程:孩子在楼梯上奔跑

Question

我开始练习动态编程，但我无法理解这个问题：

问题：

一个孩子跑上一个有n级台阶的楼梯，一次可以跳1级、2级或3级。实施一种方法来计算孩子可以跑上楼梯的可能方式。

破解编码面试书的解决方案是这样的：

"如果我们考虑到第n步的所有路径，我们可以将它们建立在前三步的路径上。我们可以通过以下任何一个到达第n站：

• 进入(n-1(步并跳1步
• 进入(n-2(步并跳2步
• 转到(n-3(步并跳3步">

要找到解决方案，只需将这些路径的数量相加即可

这就是失去我的原因为什么答案不是这样的：加上这些路径的数量，然后加上3？因为如果你在第n-1步、第n-2步或第n-3步，有3种方法可以获得第n步？我知道，如果你写下前4个基本情况的答案(假设n=0返回1(，你可以看到类似斐波那契的模式。但你可能看不到，所以这很难。

然后他们想出了这个代码：

public static int countWaysDP(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] = countWaysDP(n - 1, map) + countWaysDP(n - 2, map) + countWaysDP(n - 3, map);
return map[n]; }

}

所以我的第二个问题。当n=0时，它如何返回1。即使我接受了这个事实，如果n=1时返回0，我仍然无法找到解决它的方法。

希望这是有道理的。

谢谢

Answer 1

以下是我如何思考这个问题的-

从书-

在最后一跳，直到第n步，孩子可能完成单步、双步或三步跳。也就是说，最后移动可能是从步骤n-1开始的单步跳跃，或者是双步从n-2开始的步跃，或从n-3起的三步跃。这个因此，到达最后一步的方式的总数是达到最后三步中每一步的方法的数量

您正在正确考虑-

为什么答案不是这样的：加上这些路径的数量，然后加3？因为如果你在第n-1步、第n-2步或第n-3步，有3种方法可以第n步？

这种基本情况的问题是，只有当n>=3时，它才适用。如果只有两个步骤，那么您显然不会添加3。

让我们对个别案例进行分解，了解这里的基本案例到底是什么。

n=0

There are no stairs to climb.
Total number of ways = 0

n=1

Total number of ways = 1StepHop from (n-1)
Number of ways to do 1StepHop from Step 0(n-1) = 1
Total number of ways = 1

n=2

Total number of ways = 2StepHop from (n-2) + 1StepHop from (n-1)
Number of ways to do 2StepHop to reach Step 2 from Step 0(n-2) = 1
Number of ways to do 1StepHop to reach Step 2 from Step 1(n-1) = 1 (Previous answer for n=1) 
Total number of ways = 1 + 1 = 2

n=3

Total number of ways = 3StepHop from (n-3) + 2StepHop from (n-2) + 1StepHop from (n-1)
Number of ways to do 3StepHop to reach Step 3 from Step 0(n-3) = 1
Number of ways to do 2StepHop to reach Step 3 from Step 1(n-2) = 2 (From previous answer for n = 2)
Number of ways to do 1StepHop to reach Step 3 from Step 2 = 1 (From previous answer for n=1) 
Total number of ways = 1 + 2 + 1 = 4

---

观察-正如你从上面看到的，我们在每种情况下都正确地说明了最后一步。为n-1中的->1个StepHop、n-2的2个Stephop和n-3[/strong>的3个Stephop各添加一个。

现在来看代码，如果n=0，我们返回1的情况有点违背直觉，因为我们已经看到如果n=0-

public static int countWaysDP(int n, int[] map) {
if (n < 0) 
return 0;
else if (n == 0) 
return 1;  <------------- this case is counter-intuitive
else if (map[n] > -1)
return map[n];
else {
map[n] = countWaysDP(n - 1, map) + countWaysDP(n - 2, map) + countWaysDP(n - 3, map);
return map[n];
}

从观察中可以看出，n=0的这种反直觉情况实际上是解释最后一步的情况——1来自n-1、2来自
n-2和3来自n-3//strong>的3StepHop。

因此，点击n=0大小写只有在递归期间才有意义——只有当

n的初始值大于0这个问题的一个更完整的解决方案可能有一个驱动程序方法，该方法在核心递归算法之外处理这种情况

int countWays(int n) {
if (n <= 0 ) return 0;
int[] map = new int[n+1];
for(int i = 0; i<n+1; i++){
map[i] = -1;
}
return countWaysDP(n, map);
}

希望这会有所帮助。

Answer 2

您可以在https://github.com/CrispenGari/Triple-Step-Algorithim/blob/master/main.cpp。

int count_Ways(int n){
if(n<0){
return 0;
}else if(n==0){
return 1;
}else{
return count_Ways(n-1) +count_Ways(n-2) + count_Ways(n-3);
}
}
int main(){
cout<<"Enter number of stairs: ";
int n;
cin>>n;
cout<<"There are "<< count_Ways(n)<<"  possible ways the child can run up 
thestairs."<<endl;
return 0;
}