Jump Floor II

1. Problem Description

A frog can jump 1 step at a time, 2 steps at a time… or even n steps at a time. Find the total number of ways the frog can jump up a staircase with n steps.

2. Approach

• Formula method

// Equation 1: f(n) = f(n-1) + f(n-2) + ... + f(1)
// Equation 2: f(n-1) = f(n-2) + ... + f(1)
// Equation 1 - Equation 2 -> f(n) = 2f(n-1)

• Find the pattern

//1 1
//2 2
//3 4
//4 8
//n 2^(n-1)

3. Implementation

3.1. Formula Method

// Equation 1: f(n) = f(n-1) + f(n-2) + ... + f(1)
// Equation 2: f(n-1) = f(n-2) + ... + f(1)
// Equation 1 - Equation 2 -> f(n) = 2f(n-1)
// Time complexity: O(n)
// Space complexity: O(1)
func JumpFloorII(number int) int {
	if number == 1 {
		return number
	}

	a := 1
	res := 2 * a
	for i := 2; i < number; i++ {
		a = res
		res = 2 * a
	}
	return res
}

3.2. Find the Pattern

// Find the pattern
//1 1
//2 2
//3 4
//4 8
//n 2^(n-1)
// Time complexity: O(1)
// Space complexity: O(1)
func JumpFloorII2(number int) int {
	if number <= 1 {
		return 1
	}
	return 2 << (number - 2)
}

4. References

• Variant Climbing Stairs - NowCoder