ACM - 간단 한 문제 의 슈퍼 계단 - hdu 2041

슈퍼 계단
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 26862 Accepted Submission(s): 13830
Problem Description 한 계단 은 모두 M 급 입 니 다. 처음에 1 급 에 있 었 습 니 다. 만약 에 매번 1 급 이나 2 급 만 올 라 갈 수 있다 면 M 급 에 올 라 가 야 합 니 다. 모두 몇 가지 방법 이 있 습 니까?Input 입력 데 이 터 는 먼저 하나의 정수 N 을 포함 하고 테스트 인 스 턴 스 의 개 수 를 나타 내 며 N 줄 데 이 터 를 포함 하 며 줄 마다 하나의 정수 M (1 < = M < = 40) 을 포함 하여 계단 의 급 수 를 나타 낸다.Output 각 테스트 인 스 턴 스 에 대해 다른 주 행 법의 수량 을 출력 하 십시오 Sample Input 2 2 3 Sample Output 1
2
좋 습 니 다. 첫 번 째 반응, 재 귀, M 이 최대 40 밖 에 안 되 는 것 을 보 았 습 니 다.
그래서 과감하게 TLE,% >
비극 이 죠...나 는 여전히 너무 연하 고 너무 야 하 다.
나중에 5 조 의 데 이 터 를 계산 해 보 니 피 보 나치 수열 이 었 다.
그래서, 또 WA!!(⊙ o ⊙) 아!
설마 그렇지 않 은 가?또 생각: 설마 계산 하면 서 시 계 를 치 는 거 야?
재 귀 + 타 표 입 니 다. 먼저 앞의 3 단계 에 값 을 부여 합 니 다.
그 다음 에 i 는 4 부터 재 귀 를 시작 합 니 다. 함수 에 들 어 가 는 값 이 0 이 아니라면 배열 안의 값 을 되 돌려 줍 니 다.
결국 또 WA...어찌 할 수 없다
마지막 으로 내 초기 값 이 틀 렸 다 는 것 을 알 게 되 었 다.
내 가 책 에 쓴 1, 2, 3.중간 차 를 대표 하 는 계단 입 니 다. 저 는 첫 번 째 계단, 두 번 째 계단 이 라 고 생각 합 니 다.
고 쳤 어, 내, 과감하게 AC 야...
좋아, 내 가 너무 부주의 해서 이 문 제 는 정말 발생 해 서 는 안 돼!

//     

#include 
using namespace std;
int lt[43];

int main()
{
	int n,m,i;
	lt[1]=0;
	lt[2]=1;
	lt[3]=2;
	
	for(i=4;i<=42;++i)
		lt[i]=lt[i-1]+lt[i-2];
	cin>>n;
	while(n--)
	{
		cin>>m;
		cout<

이 거 는 재 귀 + 시계 로 만 든 거 예요.

//     

#include 
using namespace std;
int lt[43];

int search(int n)
{
	if(lt[n]!=0)
		return lt[n];
	return	search(n-1)+search(n-2);
}

int main()
{
	int n,m,i;
	lt[1]=0;
	lt[2]=1;
	lt[3]=2;
	
	for(i=4;i<=42;++i)
		lt[i]=search(i);
	cin>>n;
	while(n--)
	{
		cin>>m;
		cout<