试图解决动态规划

Question

我在已经结束的比赛中遇到了问题。下面是问题。

在Poornima 学院，PIET CS 系正在从地下室转移到三楼。该部门的 HOD 正在尝试寻找到达三楼的方法。你得到了楼梯的数量，你必须帮助 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 的新手 problems.how 我可以解决它吗？

这是一种解决方案，但是 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

嗯，这是一个很一般的动态规划谜题...假设你在第n个楼梯，那么你可以去第n个楼梯的方法数就是到达第n-1个的方法数楼梯和第 n 个楼梯！为什么？好吧，我只能通过两种方式到达第 n 层，从第 n-1 层楼梯爬一层和从第 n-2 层楼梯直接爬两层！

此外，我觉得你的问题陈述有问题，它说我们至少可以移动 0 步，这将导致到达某个楼梯的方法数量无限！为什么？我可以简单地使用无限步留在同一个楼梯上，然后移动到下一个！所以我假设你一次可以移动一个或两个楼梯

试图解决动态规划

trying to solve dynamic programming

c++

dynamic-programming