猴子爬山od

100分

题目

一天一只顽猴想要从山脚爬到山顶，途中经过一个有n个台阶的阶梯，但是这个猴子有个习惯，每一次只跳1步或3步。试问猴子通过这个阶梯有多少种不同的跳跃方式。

输入

输入只有一个数n，0 <= n <= 50，代表此阶梯有多个台阶。

输出描述

一个整数，表示有多少种跳跃方式。

示例1
输入：50
输出：122106097

示例2
输入：3
输出：2

代码思路

public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); System.out.println(countf(n)); } public static int countf(int n){ if(n<=2){ return 1; } int[] dp = new int[n+1]; dp[1]=1; dp[2]=1; dp[3]=2; for(int i=4;i<n+1;i++){ dp[i] = dp[i-1]+dp[i-3]; } return dp[n]; } }