Challenge: Frog Jumps

Lab Java Intermediate 20 points

A frog wants to reach stone n, starting on stone 0. Each jump goes forward by 1, 2 or 3 stones. In how many different ways can it get there? Use recursion with a memo – without the memo, n = 60 would take forever.

Input

One whole number n (1 ≤ n ≤ 60).

Output

The number of ways.

Example

Input

Output

Sample input available Sample output available

Editor

Java

Hints

The last jump was 1, 2 or 3 stones, so ways(n) = ways(n-1) + ways(n-2) + ways(n-3).

Base cases: ways(0) = 1, and a negative n gives 0. Store answers in a long[] memo.

Solution explanation

With the memo each ways(k) is solved once: O(n). Without it the calls grow about 1.8× per stone – billions of calls for n = 60.

Show solution

import java.util.Scanner;

public class Main {
    static long[] memo = new long[61];

    static long ways(int n) {
        if (n == 0) return 1;            // standing on the goal: one way (do nothing)
        if (n < 0) return 0;             // jumped past it: not allowed
        if (memo[n] != 0) return memo[n];
        memo[n] = ways(n - 1) + ways(n - 2) + ways(n - 3);
        return memo[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(ways(sc.nextInt()));
    }
}

Output

Answer