链接：https://ac.nowcoder.com/acm/problem/53675
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
赛时提示：保证出发点和终点都是空地
帕秋莉掌握了一种木属性魔法
这种魔法可以生成一片森林（类似于迷阵），但一次实验时，帕秋莉不小心将自己困入了森林
帕秋莉处于地图的左下角，出口在地图右上角，她只能够向上或者向右行走
现在给你森林的地图，保证可以到达出口，请问有多少种不同的方案
答案对2333取模
输入描述:
第一行两个整数m , n表示森林是m行n列
接下来m行，每行n个数，描述了地图
0 - 空地
1 - 树（无法通过）
输出描述:
一个整数表示答案
示例1
输入
3 3
0 1 0
0 0 0
0 0 0
输出
3
题目大意：
刚开始在左下方，要求只能向上或向右走，走到右上方，有1的地方不能走，求方案数对2333取模。
解题思路：
牛客小白月赛的题。用dfs写了一发超时，这道题正确的做法应该是dp，我们把问题分解成加法问题，开一个数组s，s【i,j】表示从左下走到i,j这个点的方案数是多少，当前的点i，j是由下方【i+1,j】和左边【i,j-1】的方案数相加，而【n，1】的方案数是1，我们遇到1的时候直接令这个点方案数为0就可以了，从下往上dp，最后输出s【1，n】%2333即可。
状态转移方程：dp [ i] [ j ] = dp [ i - 1 ] [ j ] + d p [ i ] [ j - 1 ]
AC代码:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 3e3+500;
int mp[N][N];
int s[N][N];
template<class T>inline void read(T &res)//快读
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')
if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')
res=res*10+c-'0';res*=flag;
}
int main()
{
int n,m;
memset(s,0,sizeof s);
read(n);
read(m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
read(mp[i][j]);
s[n][1]=1;
for(int i=n;i>=1;i--)
for(int j=1;j<=m;j++)
{
if(mp[i][j])
s[i][j]=0;
else
s[i][j]+=(s[i+1][j]+s[i][j-1])%2333;//dp公式
}
cout<<s[1][m]<<endl;
//system("pause");
return 0;
}