I Will Like Matrix!

题目

在一个 n ∗ m 的矩阵 A 的所有位置中分别填入 0 或 1，要求填入的数必须满足 Ai,j ≤ Ai,j+1 且Ai,j ≤ Ai+1,j。询问一共有多少种不同的矩阵，并将答案对 1, 000, 000, 007 取模。

输入

共一行包含两个整数 n 和 m。

输出

共一行包含一个整数 ans，表示矩阵个数模 1, 000, 000, 007 的值。

输入样例

2 2

输出样例

6

数据范围

对于 60% 的数据：n, m, k ≤ 300 对于 100% 的数据：n, m, k ≤ 5000

思路

这道题是一道DP，设f[i][j]为从矩阵的 [ i , j ] 点到矩阵的 [ n , m ] 点所组成的子矩阵的可能性，从后往前递推。

我们先来看看如何初始化。 第一，f[n][m]可以是0或者1，所以可能数为2； 接着是最后一行和列，通过推算可以看出，可能性为它下面的点或右边的点的可能性加1。

接着，我们来看看动态转移方程，可以推出，动态转移方程是$f[i][j]=(f[i+1][j]+f[i][j+1])$。

那么，最后我们输出f[1][1]就可以了。

代码

#include<cstdio> using namespace std; int n,m,f[5001][5001]; int main() { scanf("%d%d",&n,&m);//读入 f[n][m]=2;//初始化 for (int i=n-1;i>=1;i--) f[i][m]=f[i+1][m]+1;//初始化 for (int i=m-1;i>=1;i--) f[n][i]=f[n][i+1]+1;//初始化 for (int i=n-1;i>=1;i--) for (int j=m-1;j>=1;j--) f[i][j]=(f[i+1][j]+f[i][j+1])%1000000007;//动态转移方程 printf("%d",f[1][1]);//输出 return 0; }