算法题/斐波那契数列：跳楼梯

题目

给定一个有n步的楼梯，执行一种方法来计算有多少种可能的方式可以到达楼梯的顶部，给定，每一步你可以走1步，2步，或3步。

题解

暴力解法

Java

class Staircase {

  public int CountWays(int n) {
    if( n == 0)
      return 1; // 基准情况，我们不需要跳任何台阶，因此只有一个选择
      
    if(n == 1)
      return 1; // 需要跳1步台阶，因此只有一步

    if(n == 2)
      return 2; // 一次跳2步，或者跳2次1步的，有2种情况

    // 如果我们走1步，那么剩下的台阶我们要走n-1步;
    int take1Step = CountWays(n-1); 
    // 如果我们走2步，那么剩下的台阶我们要走n-2步;
    int take2Step = CountWays(n-2); 
    // 如果我们走3步，那么剩下的台阶我们要走n-3步;
    int take3Step = CountWays(n-3); 

    return take1Step + take2Step + take3Step;
  }

  public static void main(String[] args) {
    Staircase sc = new Staircase();
    System.out.println(sc.CountWays(3));
    System.out.println(sc.CountWays(4));
    System.out.println(sc.CountWays(5));
  }
}

JavaScript

class Staircase {
  countWays(n) {
    if (n === 0)
      return 1;

    if (n === 1)
      return 1;

    if (n === 2)
      return 2;

    const take1Step = this.countWays(n - 1);
    const take2Step = this.countWays(n - 2);
    const take3Step = this.countWays(n - 3);

    return take1Step + take2Step + take3Step;
  }
}

const sc = new Staircase();
console.log(sc.countWays(3));
console.log(sc.countWays(4));
console.log(sc.countWays(5));

Python

class Staircase:
  def count_ways(self, n):
    if n == 0:
      return 1

    if n == 1:
      return 1

    if n == 2:
      return 2

    take1_step = self.count_ways(n - 1)
    take2_step = self.count_ways(n - 2)
    take3_step = self.count_ways(n - 3)

    return take1_step + take2_step + take3_step

sc = Staircase()
print(sc.count_ways(3))
print(sc.count_ways(4))
print(sc.count_ways(5))

Go

package main

import "fmt"

type Staircase struct{}

func (s Staircase) CountWays(n int) int {
	if n == 0 {
		return 1
	}

	if n == 1 {
		return 1
	}

	if n == 2 {
		return 2
	}

	take1Step := s.CountWays(n - 1)
	take2Step := s.CountWays(n - 2)
	take3Step := s.CountWays(n - 3)

	return take1Step + take2Step + take3Step
}

func main() {
	sc := Staircase{}
	fmt.Println(sc.CountWays(3))
	fmt.Println(sc.CountWays(4))
	fmt.Println(sc.CountWays(5))
}

自顶向下(备忘录)

Java

class Staircase {

  public int CountWays(int n) {
    int dp[] = new int[n+1];
    return CountWaysRecursive(dp, n);
  }
  
  public int CountWaysRecursive(int[] dp, int n) {
    if( n == 0)
      return 1; // 基准情况，我们不需要跳任何台阶，因此只有一个选择
      
    if(n == 1)
      return 1; // 需要跳1步台阶，因此只有一步

    if(n == 2)
      return 2; // 一次跳2步，或者跳2次1步的，有2种情况

    if(dp[n] == 0) {
        // 如果我们走1步，那么剩下的台阶我们要走n-1步;
        int take1Step = CountWays(n-1); 
        // 如果我们走2步，那么剩下的台阶我们要走n-2步;
        int take2Step = CountWays(n-2); 
        // 如果我们走3步，那么剩下的台阶我们要走n-3步;
        dp[n] = take1Step + take2Step + take3Step;
    }
    
    return dp[n];
  }

  public static void main(String[] args) {
    Staircase sc = new Staircase();
    System.out.println(sc.CountWays(3));
    System.out.println(sc.CountWays(4));
    System.out.println(sc.CountWays(5));
  }
}

JavaScript

class Staircase {
  constructor() {
    this.dp = [];
  }

  countWays(n) {
    this.dp = new Array(n + 1).fill(0);
    return this.countWaysRecursive(n);
  }

  countWaysRecursive(n) {
    if (n === 0) {
      return 1;
    }

    if (n === 1) {
      return 1;
    }

    if (n === 2) {
      return 2;
    }

    if (this.dp[n] === 0) {
      const take1Step = this.countWaysRecursive(n - 1);
      const take2Step = this.countWaysRecursive(n - 2);
      const take3Step = this.countWaysRecursive(n - 3);
      this.dp[n] = take1Step + take2Step + take3Step;
    }

    return this.dp[n];
  }
}

const sc = new Staircase();
console.log(sc.countWays(3));
console.log(sc.countWays(4));
console.log(sc.countWays(5));

Python

class Staircase:
  def __init__(self):
    self.dp = []

  def count_ways(self, n):
    self.dp = [0] * (n + 1)
    return self.count_ways_recursive(n)

  def count_ways_recursive(self, n):
    if n == 0:
      return 1

    if n == 1:
      return 1

    if n == 2:
      return 2

    if self.dp[n] == 0:
      take1_step = self.count_ways_recursive(n - 1)
      take2_step = self.count_ways_recursive(n - 2)
      take3_step = self.count_ways_recursive(n - 3)
      self.dp[n] = take1_step + take2_step + take3_step

    return self.dp[n]

sc = Staircase()
print(sc.count_ways(3))
print(sc.count_ways(4))
print(sc.count_ways(5))

Go

package main

import "fmt"

type Staircase struct {
	dp []int
}

func (sc *Staircase) countWays(n int) int {
	sc.dp = make([]int, n+1)
	return sc.countWaysRecursive(n)
}

func (sc *Staircase) countWaysRecursive(n int) int {
	if n == 0 {
		return 1
	}

	if n == 1 {
		return 1
	}

	if n == 2 {
		return 2
	}

	if sc.dp[n] == 0 {
		take1Step := sc.countWaysRecursive(n - 1)
		take2Step := sc.countWaysRecursive(n - 2)
		take3Step := sc.countWaysRecursive(n - 3)
		sc.dp[n] = take1Step + take2Step + take3Step
	}

	return sc.dp[n]
}

func main() {
	sc := Staircase{}
	fmt.Println(sc.countWays(3))
	fmt.Println(sc.countWays(4))
	fmt.Println(sc.countWays(5))
}

自底向上

Java

class Staircase {

  public int CountWays(int n) {
    int dp[] = new int[n+1];
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;

    for(int i=3; i<=n; i++)
      dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

    return dp[n];
  }

  public static void main(String[] args) {
    Staircase sc = new Staircase();
    System.out.println(sc.CountWays(3));
    System.out.println(sc.CountWays(4));
    System.out.println(sc.CountWays(5));
  }
}

JavaScript

class Staircase {
  countWays(n) {
    let dp = new Array(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;

    for (let i = 3; i <= n; i++) {
      dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }

    return dp[n];
  }
}

let sc = new Staircase();
console.log(sc.countWays(3));
console.log(sc.countWays(4));
console.log(sc.countWays(5));

Python

class Staircase:
    def count_ways(self, n):
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1
        dp[2] = 2

        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

        return dp[n]


sc = Staircase()
print(sc.count_ways(3))
print(sc.count_ways(4))
print(sc.count_ways(5))

Go

package main

import "fmt"

type Staircase struct{}

func (s *Staircase) countWays(n int) int {
    dp := make([]int, n+1)
    dp[0] = 1
    dp[1] = 1
    dp[2] = 2

    for i := 3; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    }

    return dp[n]
}

func main() {
    sc := Staircase{}
    fmt.Println(sc.countWays(3))
    fmt.Println(sc.countWays(4))
    fmt.Println(sc.countWays(5))
}