Question

登上n级台阶,每次可以向上攀登任意奇数级台阶.共有多少种不同的方案？

登上n级台阶,每次可以向上攀登任意奇数级台阶.共有多少种不同的方案？

Answer 1

2022-03-21 重新修改了回答内容。

新的算法为一维动态规划算法，并将递归改为循环，速度比枚举算法至少高出8个数量级。递归公式和算法要点见代码的绿色字体（注释行）。

在n<200范围内，通过“枚举”和“枚举组合+排列”算法对计算结果进行了比较验证，完全正确。n>90时，结果超出64位整数，须用到大整数模块。

以下是计算结果示例和fortran代码。

追问

动态规划算法是什么
O(n)复杂度？

追答

2022-03-21

确认了递归公式，并修改为更高效率的循环算法。

计算结果也与枚举算法、枚举组合加排列算法进行了比较验证。

详见修改后的回答内容。

计算 n=10000，耗时是 18秒。结果为2090位大整数。

又写了一个不需引用大整数模块的版本，用int4整数数组替代大整数计算，计算时耗与大整数版本相当。附代码：