logo

请尝试使用动态规划算法,优化以下题目的实现代码

题目:
现有5个楼梯,台阶数分别是:10,20,30,40,45,每次可以上一个或两个台阶。请问:分别爬上这5个楼梯,每个楼梯有多少种不同的方法?
以下是该题目递归方式的实现代码(Java):

 
 
 
  1. public class Stairs {
  2. private static int climbWays(int n) {
  3. if ( n == 1 || n == 2 ) {
  4. return n;
  5. }
  6. return climbWays(n-1) + climbWays(n-2);
  7. }
  8. public static void main(String[] args) {
  9. int[] stairsArray = new int[]{10,20,30,40,45};
  10. for ( int n : stairsArray ) {
  11. long startTime = System.currentTimeMillis();
  12. int climbWays = climbWays(n);
  13. long endTime = System.currentTimeMillis();
  14. System.out.println("爬"+n+"层楼梯,有:"+climbWays+"种方法,计算耗时:"+(endTime-startTime)+"毫秒;");
  15. }
  16. }
  17. }

输出结果:
爬10层楼梯,有:89种方法,计算耗时:0毫秒;
爬20层楼梯,有:10946种方法,计算耗时:0毫秒;
爬30层楼梯,有:1346269种方法,计算耗时:4毫秒;
爬40层楼梯,有:165580141种方法,计算耗时:267毫秒;
爬45层楼梯,有:1836311903种方法,计算耗时:2852毫秒;
问题:
请尝试使用动态规划算法,优化以上题目的实现代码,降低时间复杂度。

全部回答 · 1

  • 最新
  • 最热
暂无回答
暂无回答