链接：https://ac.nowcoder.com/acm/contest/29813/K 来源：牛客网

yezzz 近日沉迷一款名为“打 Boss”的摸鱼小游戏，众所周知，游戏里面会有轻击和重击，轻击扣 Boss 一滴 血，重击扣两滴血。现在想知道若有nn轮回合，问扣 Bossmm滴血的方案数。 注意：每一回合有三种选择，轻击，重击或不攻击。

输入描述:

第一行一个整数t(1 ≤ t ≤ 10^4 )t(1≤t≤104)，表示有tt组测试数据。

接下来tt行，每行两个整数 n, m,(1 ≤ n, m ≤ 3000)n,m,(1≤n,m≤3000)表示nn轮攻击，mm滴血。

输出描述:

输出t行，第i行共包含一个整数，为第ii组测试数据的答案（由于答案过大，答案请对 1000000007 取模）。

首先是分析题目，每个回合可以有三个选择，问的是扣血的方案数

个人的感觉的话像是01背包的变形问题。

可以设置一个二维数组

int dp[3003][3003];

其实dp有时候没想象的那么难，这个题跟01背包其实就是把所有的可能都列举出来

01背包的二维数组dp[i][j]表示的是前i个物品时容量为j时装的体积

那这个稍微换一个思路就是可以分析成dp[i][j] 前i个回合，扣j滴血的方案数

然后可以从前开始分析，有三个选择。

选择不攻击的时候是这样的

dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;

选择轻击的时候，也可以想到，因为问的是i回合扣了j血的方案数，所以就是i-1回合时，扣了j-1滴血的时候再来一个轻击就是得到了方案数

dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;

由上可得，重击时跟轻击时的分析差不多，可以得到

dp[i][j]=(dp[i][j]+dp[i-1][j-2])%mod;

再把上面的整合一下就是本题的状态转移方程

dp[i][j]=(dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j])%mod;

不过有的时候要判定一下，因为j=1的时候j-2就小于0了

然后的话再放一下ac代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
long dp[3003][3003];//dp[i][j]表示i回合打j滴血的方案
int main()
{
    int t;
    cin>>t;
    dp[1][1]=1,dp[1][2]=1;
    for(int i=2;i<=3000;i++)
        dp[i][1]=(dp[i-1][1]+1)%mod;
    for(int i=2;i<=3000;i++)
        dp[i][2]=(dp[i-1][1]+dp[i-1][2]+1)%mod;
    for(int i=2;i<=3000;i++){
        for(int j=3;j<=3000;j++){
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j])%mod;
        }
    }
    while(t--){
        int n,m;
        cin>>n>>m;
        cout<<dp[n][m]<<endl;
    }
}