1388:階段を跳ぶ@jobdu
1252 ワード
タイトル1388:階段を跳ぶ
時間制限:1秒
メモリ制限:32メガ
特殊問題:いいえ
コミット:1598
解決策:641
タイトルの説明:
1匹のカエルは一度に1段の階段を飛び上がることも、2段を飛び上がることもできます.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
入力:
入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力は整数n(1<=n<=70)を含む.
出力:
各テストケースに対応し、
出力カエルがn段の階段を飛び上がるのに何種類の飛び方があるのか.
サンプル入力:
サンプル出力:
再帰が通らないので、DPを使います.
時間制限:1秒
メモリ制限:32メガ
特殊問題:いいえ
コミット:1598
解決策:641
タイトルの説明:
1匹のカエルは一度に1段の階段を飛び上がることも、2段を飛び上がることもできます.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
入力:
入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力は整数n(1<=n<=70)を含む.
出力:
各テストケースに対応し、
出力カエルがn段の階段を飛び上がるのに何種類の飛び方があるのか.
サンプル入力:
5
サンプル出力:
8
再帰が通らないので、DPを使います.
import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class S9_2 {
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(steps2(n));
}
}
public static long steps(int n){
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
return steps(n-1) + steps(n-2);
}
public static long steps2(int n){
long[] dp = new long[n+10];
dp[0] = 1;
dp[1] = 2;
for(int i=2; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n-1];
}
}