1389:変態ステップ@jobdu

タイトル1389:変態ステップ
時間制限:1秒
メモリ制限:32メガ
特殊問題:いいえ
コミット:916
解決:559
タイトルの説明:
1匹のカエルは一度に1段の階段を飛び上がることもできるし、2段も飛び上がることもできるし...n段も飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
入力:
入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力は整数n(1<=n<=50)を含む.
出力:
各テストケースに対応し、
出力カエルがn段の階段を飛び上がるのに何種類の飛び方があるのか.
サンプル入力:

6

サンプル出力:

32

フィボナッチの変形問題

import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;


public class S9_3 {
	public static void main(String[] args) throws FileNotFoundException {
		BufferedInputStream in = new BufferedInputStream(new FileInputStream("S9_2.in"));
		System.setIn(in);
		Scanner cin = new Scanner(System.in);
		
		while (cin.hasNextInt()) {
			int n = cin.nextInt();
			System.out.println(steps(n));
		}
	}
	
	public static long steps(int n){
		long[] dp = new long[n+10];
		dp[0] = 1;
		dp[1] = 2;
		for(int i=2; i<=n; i++){
			for(int j=i; j>0; j--){
				dp[i] += dp[i-j];
			}
			dp[i] += 1;
		}
		return dp[n-1];
	}
	
}