A

递推，简单dp

#include<iostream>
using namespace std;
int dp[45];
int t;
int main()
{
    cin>>t;
    dp[1]=0,dp[2]=1,dp[3]=2;
    for(int i=4;i<=40;i++)
        dp[i]=dp[i-1]+dp[i-2];
    while(t--)
    {
        int m;
        cin>>m;
        cout<<dp[m]<<endl;
    }
    return 0;
}

B

一开始我还在想怎么记录走过的路径，怎么去bfs，后来发现太复杂了
突然想到一道dp问题，和这个类似，于是考虑dp
1.状态转移：必须向右或者向下// dp[i-1][j] 或者 dp[i][j-1]
2.计算：dp[i][j] = dp[i-1][j] + dp[i][j-1]

#include<iostream>
using namespace std;
const int N=1010,mod=100003;
int a[N][N];
int dp[N][N];//dp[i][j] = dp[i-1][j] + dp[i][j-1]
int n,m;
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        a[x][y]=1;
    }
    dp[1][1]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j])
                dp[i][j]=0;
            else
            {
                if(i!=1)
                    dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;//向下
                if(j!=1)
                    dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;//向右
            }
            cout<<dp[n][n]<<endl;
    return 0;
}

C（借鉴大佬题解）

题意：给了两个串， 求将一个串转化为另一个串所需要的最小步数，每一步可以进行添加，删除， 改变这三种中的其中一种操作

个人理解：
令dp[i][j]为S的前i项，与P中的前j项匹配的最小步数解
1.相等
//s[i]==p[j]那么状态转移由上一步dp[i-1][j-1]转移而来
2.不相等，需要改动
//修改操作则上一步dp[i][j]=dp[i-1][j-1]+1
//删除s[i]或者添加p[j]==   dp[i][j]=dp[i-1][j]+1
//删除p[j]或者添加s[i]==   dp[i][j]=dp[i][j-1]+1
3.有一个字符串为空的情况（初始化）
//如果i==0或者j==0的时候，操作数都是删除的，次数等于i或者j的大小

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=1e3+5;
int dp[N][N];
char s[N];
char p[N];
int main()
{
    int n,m;

    while(cin >> n >> s+1 >> m >> p+1)
    {
        memset(dp,0,sizeof dp);
        for(int i=0;i<=m;i++)//初始化
        {//注意这个初始化，dp[0][1]=1删除一次就可以，dp[0][2]删除两次
        //以此类推，如果不初始化，则会忽略情况
            dp[0][i]=i;
        }
        for(int i=0;i<=n;i++)
        {
            dp[i][0]=i;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(s[i]==p[j])
                {
                    dp[i][j]=dp[i-1][j-1];
                }else
                {
                    dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
                }
            }
        }
        cout << dp[n][m] << endl;
    }
}