昨天好几道题没做出来很郁闷，结果今天上来半小时不到就直接做出一道黄DP题了，不错，又有写题的冲动了。
这道题我一直被那个“因为方案数可能很多，请输出方案数对 1000007取模的结果。”这句话吓到了，因为我在想如果涉及求最优方案，那么势必会有比较，那么既然取了摸还怎么比较啊？不会另要开一个数组记录每一个dp数组的值取过的有效模（即取模前后大小不一样就算是一次有效模）的数量吧，然后依照有效模数量和数值来比较，那也太麻烦了。而且昨天刚做题不顺很郁闷就不想写了。
但是突然意识到这道题求总方案数似乎并不需要涉及大小比较啊，就无脑的记忆化搜索把所需情况都加起来不就得了，每求一个加法都来一个取模运算，根本不用管那个取模的事情，毕竟只要让取模的题应该大概率都不需要比较，因为一旦需要比较就需要我上面想出来的那个方法来解决，这太麻烦了思维强度却不高，因而没有考核意义。
总之就是别做题前想着这个那个的，先写记搜的状态转移方程，然后在看到底能不能行，很多时候自己担忧的问题写出初步代码后就会发现其实没啥可担忧的根本不是问题，总之就是大胆的写起来。
顺便，此前一直不是很确定边界条件应该怎么搞，这道题让我想明白了——同样，先把记搜的状态转移写出来，然后自然而言就知道了到底是第一行、还是第一列、还是第一行和第一列需要设置边界条件、以及这个第一行和第一列是从下标0开始还是1开始等等等等，这些问题写出状态转移后自然非常清楚的看一眼便知。
就这样，上代码！
CODE
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#define int long long
using namespace std;
int dp[105][105],a[105],n,m;
int dfs(int spe,int qua)//species and quantity
{
if(dp[spe][qua]!=-1)return dp[spe][qua];
if(qua==0)return dp[spe][qua]=1;
if(spe==1)
{
if(qua<=a[spe])
return dp[spe][qua]=1;
else
return dp[spe][qua]=0;
}
//先写状态转移，再状态状态转移方程来发现我需要特设什么边界条件
int DFS=0;
for(int i=0;i<=a[spe];i++)
{
if(qua-i>=0)
DFS=(DFS+dfs(spe-1,qua-i))%1000007;
}
return dp[spe][qua]=DFS;//需要取模大多不需要大小比较只需要加减法，因此别担心放心写就是了。
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
memset(dp,-1,sizeof(dp));
cout<<dfs(n,m)<<endl;
/*
cout<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<dfs(i,j)<<' ';
cout<<endl;
}*/
return 0;
}