相关疑难解决方法(0)

我在接受采访时遇到了以下问题:

给定一个有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

但是,在采访中,我没有为此编写非常好的代码.你会如何编写这个问题的解决方案？

谢谢!

如果初始值是一些任意数字,如果1,2 3即T(1)= 1,T(2)= 2和T(3)= 3,如何用矩阵乘法法找到第n个tribonacci数.

如果T(n)= T(n-1)+ T(n-2)+ T(n-3)那么如果n非常大,如何找到T(n),如果有人能用矩阵解释我会很感激乘法方法.如何构造初始矩阵.

一个人正在跑步一个有n个台阶的楼梯,可以一次走1步,2步或3步.现在编写一个程序来计算孩子跑楼梯的可能方式.

给出的代码如下

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.这是来自Cracking the Coding的采访书.任何人都可以解释一下

1. 她为什么以及如何在这里使用功能图？这里的地图是阵列对吗？

2. 我没有看到任何行保存输入到地图数组,但它会如何返回一些东西？

3. 有人知道这段代码的C++或C版本吗？很难理解这段代码.也许不是因为JAVA语法,而是动态编程的隐式结构.

4. 这个算法的时间复杂度是多少？它应该小于O(3 ^ n)？

我将不胜感激.

多谢你们