Triple Step

作者 QIFAN 日期 2016-10-01
Triple Step

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步楼梯可以由:

  • 第n-1步 + 1 步
  • 第n-2步 + 2 步
  • 第n-3步 + 3 步

Base case:若n < 0,返回0;若n == 0, 返回1;

解题

  • 使用缓存数组

    public int countWays(int n) {
    // 新建一列数组来存储之前的步数,避免重复运算
    int[] memo = new int[n+1];
    // 设置初始值为-1
    Arrays.fill(memo, -1);
    return countWays(n, memo);
    }
    public int countWays(int n, int[] memo) {
    if(n < 0) return 0;
    if(n == 0) return 1;
    if(memo[n] > -1) return memo[n];
    memo[n] = countWays(n - 1, memo) + countWays(n - 2, memo) + countWays(n - 3, memo);
    return memo[n];
    }
  • 不使用

    public int countWays(int n) {
    if(n < 0) return 0;
    if(n == 0) return 1;
    return countWays(n - 1) + countWays(n - 2) + countWays(n - 3);
    }

分析

  • 使用缓存数组:
    时间复杂度为O(N)
    空间复杂度为O(N)

  • 不使用:
    时间复杂度为O(3^N)
    空间复杂度为O(1)