原题连接
记忆深搜
import java.util.Scanner;
import java.util.Arrays;
class Main{
static int[][] DiGong;
static int[][][][]jilu;//因为int类型可以存21亿,又要对1000000007进行取模,因此int数据类型就可以了
//但是注意在存进去这个表里之前的值可能会超出int范围,因此设置一个long类型的数据变量用来
static int n,m,k;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n=sc.nextInt();m=sc.nextInt();k=sc.nextInt();
DiGong = new int[n+1][m+1];
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) DiGong[i][j]=sc.nextInt();
chushihua();
long result=dfs(0,1,1,-1);//关键点,当没拿东西时,最大的物品价值应该是-1而不是0,因为有的物品价值可能是0
System.out.println(result%1000000007);
}
public static void chushihua() {
jilu = new int[n+1][m+1][12+1][12+2];//因为k最多只能有12个,所以设为12+1。而价值最大为12,且因为价值为-1存在下标为0的位置,以此类推.故设为12+2
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int num=0;num<=k;num++)
Arrays.fill(jilu[i][j][num], -1);
}
public static int dfs(int num,int nowN,int nowM,int max) {
long result=0;
if(jilu[nowN][nowM][num][max+1]!=-1)return jilu[nowN][nowM][num][max+1];
if(nowN==n&&nowM==m) {
if(num==k||(max<DiGong[n][m]&&num==k-1))return jilu[nowN][nowM][num][max+1]=1;
else return jilu[nowN][nowM][num][max+1]=0;
}
if(nowM<m) {
if(DiGong[nowN][nowM]>max&&num<k) result+=dfs(num+1,nowN,nowM+1,DiGong[nowN][nowM]);
result+=dfs(num,nowN,nowM+1,max);
}
if(nowN<n) {
if(DiGong[nowN][nowM]>max&&num<k)result+=dfs(num+1,nowN+1,nowM,DiGong[nowN][nowM]);
result+=dfs(num,nowN+1,nowM,max);
}
return jilu[nowN][nowM][num][max+1]=(int)(result%1000000007);
}
}