Planar Reflections

​​C - Planar Reflections​​

參考：Codeforces 1498C - Planar Reflections （DP）

對于 dp 而言，就是要發現其中可以遞推的東西。

\(dp[i][j]=dp[n-i][j-1](表示反射的粒子)+dp[i-1][j](表示穿過的粒子)\)

第一維狀态表示剩餘的要穿過的層數，第二緯表示目前粒子的衰變年齡。

// Created by CAD
#include <bits/stdc++.h>
#define mst(name, value) memset(name,value,sizeof(name))
using namespace std;

int dp[1005][1005];
int n;
const int mod=1e9+7;

int dfs(int i, int j){
    if(~dp[i][j]) return dp[i][j];
    if(j==1||i==0) return dp[i][j]=1;
    return dp[i][j]=(1ll*dfs(n-i,j-1)+dfs(i-1,j))%mod;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;cin>>t;
    while(t--){
        mst(dp,-1);
        int k;cin>>n>>k;
        cout<<dfs(n,k)<<endl;
    }
    return 0;
}