HDU 2041 슈퍼 계단(dp)

1669 단어
Description에는 모두 M급이 있습니다. 처음에 당신은 1급에 있었습니다. 만약에 매번 1급이나 2급만 올라갈 수 있다면 M급을 올라가야 합니다. 모두 몇 가지 걷는 방법이 있습니까?Input 입력 데이터는 먼저 하나의 정수 N을 포함하고 테스트 실례의 개수를 나타낸다. 그 다음에 N 줄 데이터로 한 줄에 하나의 정수 M(1<=M<=40)을 포함한다. 계단의 급수 Output은 각 테스트 실례에 대해 서로 다른 걸음걸이의 수량을 출력해 주십시오. Sample Input 2 2 3 Sample Output 1 2 Solution 클래식 dp는 dp[n]로 n급의 계단에 오르는 방법이 몇 가지가 있는지 나타낸다. 분명히 n-1급 또는 n-2급에서 n급,그래서 쉽게 전이 방정식 dp[n]=dp[n-1]+dp[n-2]코드가 나온다.
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
    int dp[44];
    dp[0]=dp[1]=1;
    for(int i=2;i<44;i++)
        dp[i]=dp[i-1]+dp[i-2];
    int t;
    cin>>t;
    while(t--)
    {
        int temp;
        cin>>temp;
        cout<<dp[temp-1]<<endl;
    }
    return 0;
} 

좋은 웹페이지 즐겨찾기