题意：
X 国王有一个地宫宝库，是 n×m 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是 k 件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 k 件宝贝。
输入格式
第一行 3 个整数，n,m,k，含义见题目描述。
接下来 n 行，每行有 m 个整数 Ci 用来描述宝库矩阵每个格子的宝贝价值。
输出格式
输出一个整数，表示正好取 k 个宝贝的行动方案数。
该数字可能很大，输出它对 1000000007 取模的结果。
数据范围
1≤n,m≤50，1≤k≤12，0≤Ci≤12
解法：
发现数据范围比较小，直接
4维dp即可，
令
dp(i
,j
,cnt
,ma
)表示当前在
(i
,j
)上，身上cnt件物品，物品的最大值为ma的方案数。
状态总数为
50*50*12*13<4e5
code：
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int maxm
=55;
const int mod
=1e9+7;
ll d
[55][55][15][15];
ll a
[55][55];
ll n
,m
,k
;
signed main(){
scanf("%lld%lld%lld",&n
,&m
,&k
);
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=m
;j
++){
scanf("%lld",&a
[i
][j
]);
a
[i
][j
]++;
}
}
d
[1][1][1][a
[1][1]]=1;
d
[1][1][0][0]=1;
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=m
;j
++){
for(int now
=0;now
<=k
;now
++){
for(int ma
=0;ma
<=13;ma
++){
if(i
+1<=n
){
d
[i
+1][j
][now
][ma
]=(d
[i
+1][j
][now
][ma
]+d
[i
][j
][now
][ma
])%mod
;
if(a
[i
+1][j
]>ma
){
d
[i
+1][j
][now
+1][a
[i
+1][j
]]=(d
[i
+1][j
][now
+1][a
[i
+1][j
]]+d
[i
][j
][now
][ma
])%mod
;
}
}
if(j
+1<=m
){
d
[i
][j
+1][now
][ma
]=(d
[i
][j
+1][now
][ma
]+d
[i
][j
][now
][ma
])%mod
;
if(a
[i
][j
+1]>ma
){
d
[i
][j
+1][now
+1][a
[i
][j
+1]]=(d
[i
][j
+1][now
+1][a
[i
][j
+1]]+d
[i
][j
][now
][ma
])%mod
;
}
}
}
}
}
}
int ans
=0;
for(int i
=0;i
<=13;i
++){
ans
=(1ll*ans
+d
[n
][m
][k
][i
])%mod
;
}
printf("%d\n",ans
);
return 0;
}
