问题描述
一个男人跑起来有n个楼梯，并能去任何1步，2步，或3个步骤的时间。现在写一个程序来计算有多少可能的方式，孩子可以跑楼梯。
A man is running up a staircase with n steps, and can go either 1 steps, 2 steps, or 3 steps at a time. Now write a program to count how many possible ways the child can run the stairs.
给出的code是象下面
The code given is like below
public static int countDP(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] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);
return map[n]; }
}
我知道C和C ++，而不是Java。这是从破解编码面试的书。有谁可以解释
I know C and C++, not JAVA.This is from the Cracking the Coding interview book.Could anybody can explain
-
为什么和怎样，她用功能的地图吗？地图在这里是数组吧？
why and how she employs the function map here? map here is array right?
我看不到任何线，以节省输入到地图数组但如何将它返回的东西？
I do not see any line to save an input to the map array but how would it return something?
任何人都有的C一个想法，这个code ++或C版本？这是很难理解这一点code。也许不是因为Java的语法，而是动态规划的隐结构的
Anybody has an idea of C++ or C version of this code? It is hard to understand this code. Maybe not because of the JAVA grammar, but the implicit structure of dynamic programming.
什么是该算法的时间复杂度？它应该比O（3 ^ n）的小？
What would be the time complexity of this algorithm? It should be smaller than O(3^n) ?
我将不胜AP preciate吧。
I would greatly appreciate it.
谢谢你们
推荐答案
好了，这是什么code一样。
Okay, here is what the code does.
`if (n<0)`
`return 0;`
如果有没有保持足够的步骤，那么不要指望它。举例来说，如果有剩余的两个步骤，但用户正试图采取三个步骤，那么它不计数作为一个可能的组合。
If there aren't enough steps remaining, then don't count it. For instance, if there are two steps remaining, but the user is trying to take three steps, then it does not count as a possible combination.
否则，如果（N == 0） 返回1;
如果剩余步骤数可用的步骤的用户正试图采取的数量匹配，这是一个可能的组合。所以，返回1，因为这是一个可能的组合，并应被添加到有效组合的总数。
If the number of steps remaining matches the number of available steps the user is trying to take, it is a possible combination. So, return a 1 because this is a possible combination and should be added to the total number of valid combinations.
否则，如果（图[N]＆GT; -1） 返回地图[N];
下面是动态规划的一部分。假定所有的数组中的值具有值-1。所以，如果该数目大于-1，它已经被解决了，所以从步数返回解决它的组合总数n代替
Here is the dynamic programming part. Assume that the all the values in the array had a value of -1. So, if the number is greater than -1, it has already been solved for, so return the total number of combinations from step number n instead of resolving it.
`map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);`
返回地图[N]; }
最后，这部分解决了code。可能的组合的数量等于可能的组合，如果他需要1步+可能的组合，如果他需要2步+可能的组合的号码，如果他需要，用户可以得到用户可以得到一些用户可以得到数三个步骤。
Finally, this part solves the code. The number of possible combinations is equal to the number of possible combinations the user can get if he takes 1 step + the number of possible combinations the user can get if he takes 2 steps + the number of possible combinations the user can get if he takes three steps.
一个例子，假设有5个步骤
An example, suppose there are 5 steps
一个简单的运行将如下所示：
A simple run would look like:
//The number of solutions from the fifth step
countDp(5) = countDp(4)+countDp(3)+countDp(2);
//Number of solutions from the fourth step
countDP(4) = countDp(3)+countDp(2)+countDp(1);
//Number of solutions from the third step
countDp(3) = countDp(2)+countDp(1)+countDp(0);
//Number of solutions from the second step
countDp(2) = countDp(1)+countDp(0)+countDp(-1);
//Number of solutions from the first step
countDp(1) = countDp(0) + countDp(-1)+countDp(-2);
//Finally, base case
countDp(0) = 1;
countDp(-1)= 0;
countDp(-2)= 0;
countDp(1) = 1+0+0 = 1;
countDp(2) = 1+1+0 = 2; //Dynamic programming: did not have to resolve for countDp(1), instead looked up the value in map[1]
countDp(3) = 2+1+1 = 4; //Dynamic programming, did not have to solve for countDp(1), countDp(2), instead looked up value in map[1] and map[2]
countDp(4) = 4+2+1=7 //Dynamic programming, did not have to solve for CountDp(3),CountDp(2), CountDp(1), just looked them up in map[3],map[2],map[1]
countDp(5)= 2+4+7=13 //Dynamic programming, just used map[4]+map[3]+map[2]
这篇关于Java编程：楼梯例如动态规划的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！