пытается решить динамическое программирование

Question

У меня проблема с конкурсом, который уже закончился. Ниже приведен вопрос.

В колледже Poornima PIET CS Deparment смещается из подвала на третий этаж. Ход отдела пытается найти число способов добраться до третьего этажа. Вам дается количество лестниц, и вы должны помочь HOD узнать количество способов, которыми он может подняться по лестнице. HOD способен подняться максимум на две ступени за раз и минимум на нуль.

Input:The first line contains the number of test cases, T. 
T lines follow, each of which contains total number of stairs. 

Output: 
Print the total number of possible ways to climbing the stairs. 

Constraints: 
1<=T<=100 
1<=N<=100 

Sample Input(Plaintext Link) 
3 
1 
2 
4 
Sample Output(Plaintext Link) 
1 
2 
5 
Explanation 
Input: n = 1 
Output: 1 
There is only one way to climb 1 stair 

Input: n = 2 
Output: 2 
There are two ways: (1, 1) and (2,0) 

Input: n = 4 
Output: 5 
(1, 1, 1, 1), (1, 1, 2,0), (2, 1, 1,0), (1, 2, 1,0), (2, 2,0,0) are the only four ways to climb stairs. 

Я уверен, что решение может быть достигнуто с помощью DP. но я попытался и не смог. Я новичок в решении проблем DP. Как я могу это решить?

вот одно решение, но как получается эта формула DP?

#include<cstdio> 
#include<iostream> 
#include<vector> 
#include<utility> 
#include<string.h> 
#include<algorithm> 
#include<cmath> 

#define LL long long int 
#define s(a) scanf("%d",&a) 

#define ss(a) scanf("%s",a) 
#define w(t) while(t--) 
#define f(i,n) for(i=0;i<n;i++) 
#define fd(i,n) for(i=n-1;i>=0;i--) 
#define p(a) printf("%d",a) 

#define ps(a) printf("%s",a) 
#define pc(a) printf("%c",a) 
#define ent printf("\n") 
bool wayToSort(int i, int j) { return i > j; } 
using namespace std; 
long long int dp[1005]; 
int main() 
{ dp[0]=0; 
    dp[1]=1; 
    dp[2]=2; 
    int t,i,j,n; 
    for(i=3;i<=1000;i++) 
    { 
     dp[i]=dp[i-1]+dp[i-2]; 
    } 
    s(t); 
    w(t) 
    { 
     s(n); 
     cout<<dp[n]<<endl; 
    } 
    return 0; 
} 

Answer 1

Ну, это очень общее динамическое программирование головоломки ... Предположим, вы на п-й ступеньке, то число способов, которыми Вы можете перейти к п-й ступеньке это число способов достигнуть н- 1-я лестница и n-я лестница! Почему? Ну, я могу добраться до n-й лестницы всего в двух путях от n-й лестницы, поднимающейся по одной лестнице, и с n-2-й лестницы, поднимающейся на два прямо!

Morover Я чувствую проблему с вашим заявлением о проблемах, он говорит, что мы можем, как минимум, перемещать 0 шагов, что приведет к тому, что количество способов достичь бесконечной лестницы! Зачем? Я могу просто использовать бесконечные шаги, чтобы остаться на одной и той же лестнице, а затем перейти к следующей! Поэтому я предположил, что вы можете переместить одну или две лестницы за один раз