【汕头市选2012初中组】数数(count)
(File IO): input:count.in output:count.out
题目描述
ftiasch 开发了一个奇怪的游戏，这个游戏的是这样的：一个长方形，被分成N 行M 列的格子，第i 行第j 列的格子记为(i, j)，就是说，左上角的格子是(1,1)，右下角的格子是(N,M)。开始的时候，nm 在(1,1)，他需要走到(N,M)。每一步，nm 可以走到正右方或者正下方的一个格子。具体地说，如果nm 现在在(x, y)，那么他可以走到(x,y + 1) 或(x + 1,y)。当然，nm 不能走出离开这个长方形。
每个格子有积分，用一个1—10 的整数表示。经过这个格子，就会获取这个格子的积分（起点和终点的积分也计算）。通过的方法是：到达(N,M) 的时候，积分恰好为P。
现在给出这个长方形每个格子的积分，你需要帮助nm，求出从起点走到终点，积分为P的线路有多少条。
输入
第1 行，3 个整数N, M, P。接下来N 行，每行M 个整数Aij，表示格子(i, j) 的积分。
输出
1 行，1 个整数，表示积分为P 线路的数量。因为数值太大，你只需要输出结果除以(10^9 +7) 的余数。
样例输入
3 3 9
2 2 1
2 2 2
1 2 2
样例输出
2
数据范围限制
对于50% 的数据，1<= N,M<=10。
对于100% 的数据，1<=N,M<=100，0 <= Aij<=10。
俗话说暴力出奇迹，简单的
第一步：找dp式
作文开头难，写好开头成一半。动态规划式就是dp算法的核心，如果要用动态规划，写好了动态规划式，也就已经有了一半了。但正因如此，动态规划式是整个算法里最难，也是最难理解的部分。
因为nm可以走到正右方或者正下方的一个格子，所以每一个格子的路径数取决于它上面的格子和左边的格子，nm从上面的格子和左边的格子到达当前格子都行，所以dp式为，解释一下第三项p-a[i][j]，因为当前分数为p，所以走到这个格子之前，分数就为p-a[i][j]。
第二步：实现
我们设dp[1][1][a[1][1]]初值为1，因为从起点出发到起点，分值为起点的积分数（起点和终点的积分也计算）只有一种方案，然后我们for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)，说人话就是从左到右、从上到下遍历，为什么一定要酱紫？因为每一个格子的路径数取决于它上面的格子和左边的格子，所以一定要保证一个格子计算之前，它上面的格子和左边的格子已经计算了（当然，如果一列列遍历也行，但过于繁琐
最后：注意事项
要记得把答案模10^9+7，但不是最后才模，不然可能还没有模就已经爆掉了，要在计算的时候，也就是
香香的小狗
原创文章 6获赞 6访问量 74
关注
私信
展开阅读全文
作者：香香的小狗
