标题：地宫取宝
X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。
【数据格式】
输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)
接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值
要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。
例如，输入：
2 2 2
1 2
2 1
程序应该输出：
2
再例如，输入：
2 3 2
1 2 3
2 1 5
程序应该输出：
14
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。
解析：
方案一：
static int n; //矩阵n行
static int m; //矩阵m列
static int k; //要求取宝贝的数量
static int[][] arr; //定义矩阵的二维数组
static long result=0; //答案
//rowIndex:当前X轴坐标;colIndex:当前Y轴坐标;
//max:行走过程中最大价值;count:手中宝贝数量
public static void move(int rowIndex,int colIndex,int max,int count)
{
if(rowIndex >= n || colIndex >= m || count > k) //当走出矩阵或者宝贝数量过多则退出函数
return;
if(rowIndex == n-1 && colIndex == m-1) //走到最后一格格子
{
//当宝贝数量已经符合题意，则最后一次不拿宝贝
//当宝贝差一个并且最后一格格子价值高于最大值，则拿起最后一格宝贝符合题意
if(count == k || (count == k-1 && arr[rowIndex][colIndex] > max))
{
result++;
result = result % 1000000007;
}
}
if(arr[rowIndex][colIndex] > max) //当前格子价格大于任意宝贝价格
{
move(rowIndex+1,colIndex,arr[rowIndex][colIndex],count+1); //右走,拿起宝贝
move(rowIndex+1,colIndex,max,count);//右走,不拿宝贝
move(rowIndex,colIndex+1,arr[rowIndex][colIndex],count+1); //下走,拿起宝贝
move(rowIndex,colIndex+1,max,count); //下走，不拿宝贝
}
else
{
move(rowIndex+1,colIndex,max,count);//右走,不拿宝贝
move(rowIndex,colIndex+1,max,count); //下走，不拿宝贝
}
}
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
n = input.nextInt(); //矩阵n行
m = input.nextInt(); //矩阵m列
arr = new int[n][m]; //定义矩阵的二维数组
k = input.nextInt(); //取K件宝贝
//循环输入矩阵中每件宝贝的价值
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
arr[i][j] = input.nextInt();
}
}
move(0,0,-1,0); //max值给-1因为宝物价值可以为0
System.out.println(result );
}
方案一有很多重复递归计算，效率较低，例如，如下数组：
1 2 3
4 5 6
7 8 9
如果数据定位在5的位置，并且递归函数的四个参数完全相同的情况下，也就是坐标相同，最大值相同，宝贝数量也相同，只需要向里层递归一次求得结果即可，不需要每次重复递归计算。
方案二：
（1）定义四维数组，存储递归函数四个参数取不同值的时候到右下角的方案数量，即答案，判断是否经历过计算，避免重复计算，提高运行效率。
（2）1到9的数量=2到9数量+4到9的数量；2到9数量=3到9的数量+5到9的数量；......,所以在每次递归调用的时候进行累加计算。
static int n; //矩阵n行
static int m; //矩阵m列
static int k; //要求取宝贝的数量
static int[][] arr; //定义矩阵的二维数组
static long data[][][][] = new long[55][55][15][15];
//rowIndex:当前X轴坐标;colIndex:当前Y轴坐标;
//max:行走过程中最大价值;count:手中宝贝数量
public static long move(int rowIndex,int colIndex,int max,int count)
{
if(data[rowIndex][colIndex][max+1][count] != -1)
return data[rowIndex][colIndex][max+1][count];
long result=0; //答案
if(rowIndex >= n || colIndex >= m || count > k) //当走出矩阵或者宝贝数量过多则退出函数
return 0;
if(rowIndex == n-1 && colIndex == m-1) //走到最后一格格子
{
//当宝贝数量已经符合题意，则最后一次不拿宝贝
//当宝贝差一个并且最后一格格子价值高于最大值，则拿起最后一格宝贝符合题意
if(count == k || (count == k-1 && arr[rowIndex][colIndex] > max))
return 1;
return 0;
}
if(arr[rowIndex][colIndex] > max) //当前格子价格大于任意宝贝价格
{
result += move(rowIndex+1,colIndex,arr[rowIndex][colIndex],count+1); //右走,拿起宝贝
result += move(rowIndex+1,colIndex,max,count);//右走,不拿宝贝
result += move(rowIndex,colIndex+1,arr[rowIndex][colIndex],count+1); //下走,拿起宝贝
result += move(rowIndex,colIndex+1,max,count); //下走，不拿宝贝
}
else
{
result += move(rowIndex+1,colIndex,max,count);//右走,不拿宝贝
result += move(rowIndex,colIndex+1,max,count); //下走，不拿宝贝
}
//System.out.println(rowIndex+","+colIndex+","+max+","+count+"="+result);
data[rowIndex][colIndex][max+1][count] = result%1000000007;
return result;
}
//初始化data数据全部为-1
public static void InitData()
{
for (int a = 0; a < 55; a++) {
for (int b = 0; b < 55; b++) {
for (int c = 0; c < 15; c++) {
for (int d = 0; d < 15; d++) {
data[a][b][c][d] = -1;
}
}
}
}
}
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
n = input.nextInt(); //矩阵n行
m = input.nextInt(); //矩阵m列
arr = new int[n][m]; //定义矩阵的二维数组
k = input.nextInt(); //取K件宝贝
//循环输入矩阵中每件宝贝的价值
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
arr[i][j] = input.nextInt();
}
}
InitData();
long r = move(0,0,-1,0); //max值给-1因为宝物价值可以为0
System.out.println(r );
}
