在楼梯上递归 [英] Recursion on staircase
问题描述
我试图理解一本书中针对以下问题的解决方案：
I'm trying to understand the solution provided in a book to the following question:
一个孩子正爬上n级台阶，可以跳
"A child is running up a staircase with n steps and can hop either 1 step, 2 steps or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs."
这本书的解决方案是紧随其后的是，最后一步可能是从n-1开始的单步跳跃，从n-2步骤开始的双步跳跃或从n-3步骤开始的三步跳跃
The book's solution is as follows, stemming from the fact that "the last move may be a single step hop from n - 1, a double step hop from step n - 2 or a triple step hop from step n - 3"
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]; }
}
我的困惑是：
-
如果步数为零，为什么程序应该返回1？我的思考方式是，如果步骤数为零，则有零种方法可以穿越楼梯。
Why should the program return 1 if the number of steps is zero? The way I think about it, if the number of steps is zero, then there are zero ways to traverse the staircase. Wouldn't a better solution be something like "if (n <= 0) return 0; else if (n == 1) return 1"?
我不确定我是否理解将其变为静态方法的原理？ Google说，静态方法是整个类而不是类的对象调用的方法。因此，本书的意图似乎是这样的：
I'm not sure I understand the rationale behind making this a static method? Google says that a static method is one that is called by the entire class, and not by an object of the class. So the book's intention seems to be something like:
。
class Staircase {
static int n;
public:
static int countWaysDP(int n, int[] map); }
而不是：
class Staircase {
int n;
public:
int countWaysDP(int n, int[] map); }
为什么？全班实例化多个楼梯是什么问题？
Why? What's the problem with there being multiple staircases instantiated by the class?
谢谢。
（注意：本书正在破解编码面试）
(Note: Book is Cracking the Coding Interview)
推荐答案
答案2：
静态方法意味着该函数不需要该对象的任何信息。
Answer 2: A Static method means the function doesn't need any information from the object.
该函数仅接受输入（在参数中），对其进行处理并返回某些内容。
当您在函数中看不到任何 this时，可以将其设置为静态。
The function just takes an input (in the parameters), processes it and returns something. When you don't see any "this" in a function, you can set it as static.
非静态方法通常读取某些属性（此变量）和/或将值存储在某些属性中。
Non-static methods usually read some properties (this-variables) and/or store values in some properties.
答案1：
我将其转换为javascript，只是为了说明会发生什么。
Answer 1: I converted this to javascript, just to show what happens.
http://jsbin.com/linake/1/edit?html,js,output
我想这就是重点。递归通常与您期望的相反。它通常以相反的顺序返回值。
对于5个楼梯：
首先返回n = 1；那么n = 2，...直到n = 5；
n = 5必须等到n = 4准备好，n = 4必须等到n = 3准备好，...
I guess this is the point. Recursion often works opposite to what you could expect. It often returns values in the opposite order.
For 5 staircases:
First it returns n=1; then n=2, ... up to n=5;
n=5 has to wait until n=4 is ready, n=4 has to wait until n=3 is ready, ...
所以这是您的n = 0和n <0：
函数的第一个返回值为n = 1;
So here is your n=0 and n<0: The first return of the function has n=1; that calls this
map[n] = countWaysDP(n - 1, map) + countWaysDP(n - 2, map) + countWaysDP(n - 3, map)
所以
map[n] = countWaysDP(0, map) + countWaysDP(-1, map) + countWaysDP(-2, map)
countWaysDP（0，map）返回1;其他术语毫无意义，因此它们返回0。这就是为什么n == 0和n <0
There countWaysDP(0, map) returns 1; the other terms are meaningless, so they return 0. That's why there are these clauses for n==0 and n<0
注意这些子句的原因，您可以添加
notice, you can add
+ countWaysDP(n - 4, map)
如果您想看看孩子也可以跳4例的情况
if you want to see what happens when the child can also jump 4 cases
也请注意：
正如我在回答中所说2，您会看到此函数不需要任何对象。它只是处理数据并返回某些内容。
因此，在您的情况下，在您的类中具有此功能很有用，因为您的功能已分组（它们不仅是散布在脚本中的松散功能），而且使其变为静态意味着编译器不必携带围绕对象的内存（尤其是对象的属性）。
Also notice: As I said in answer 2, you see this function doesn't require any object. It just processes data and returns something. So, in your case, having this function in your class is useful because your functions are grouped (they 're not just loose functions scattered around your script), but making it static means the compiler doesn't have to carry around the memory of the object (especially the properties of the object).
我希望这是有道理的。当然，有些人可以给出更准确的答案。我在回答这个问题时有点生气（我主要使用JavaScript）。
I hope this makes sense. There are surely people that can give more accurate answers; I'm a bit out of my element answering this (I mostly do javascript).
这篇关于在楼梯上递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
