지하 궁전 에서 보물 을 채취 하 다.

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 에 대한 결 과 를 출력 할 수 있 습 니 다.예 를 들 어 입력: 22 21 22 1 프로그램 은 출력 해 야 합 니 다. 2. 예 를 들 어 입력: 23 21 2 32 1 5 프로그램 은 출력 해 야 합 니 다. 14.
사고방식: 이 문 제 를 처음 접 했 을 때 가장 먼저 생각 나 는 것 은 모든 가능성 을 귀속 시 키 는 것 이다. 그러나 그 중에서 대량의 중복 계산 이 존재 한다. 데이터 가 너무 크 면 시간 을 초과 할 수 있다 (코드 는 다음 과 같다). 그 다음 에 다른 사람의 코드 를 참고 하여 기억 으로 검색 하고 싶다.
코드 1 (권장 하지 않 음 참고 만 제공)

#include 
#define MAX 1000000007
#define M 51
int values[M][M]={0};
int n=0,m=0,k=0;
int count=0;
void search(int own,int max,int x,int y);
int main(void)
{
	int i=0,j=0;
	scanf("%d %d %d",&n,&m,&k);
	for(i=0;i=n||y>=m||own>k) return;
	if(x==n-1&&y==m-1&&(own==k||own==k-1&&values[x][y]>max))
	{
		count++;
		count = count%MAX;
		return;
	}
	if(values[x][y]>max)
	{
		search(own+1,values[x][y],x+1,y);
		search(own+1,values[x][y],x,y+1);
	}
	search(own,max,x+1,y);
	search(own,max,x,y+1);
}

코드 2 (기억 검색, dfs):

#include 
#include 
#define M 55
#define N 15
#define MOD %1000000007
int State[M][M][N][N]; //    ，n ，m ，     own，      max 
int values[M][M]={0}; //          
int n=0,m=0,k=0;
int search(int x,int y,int own,int max);
int main(void)
{
	memset(State,-1,sizeof(State));  //            -1（   0） 
	int i=0,j=0;
	scanf("%d %d %d",&n,&m,&k);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			scanf("%d",*(values+i)+j);
		}
	}
	printf("%d",search(1,1,0,-1));
	return 0;
}

int search(int x,int y,int own,int max)
{
	//    -1，        （      ） 
	if(State[x][y][own][max+1]!=-1) return State[x][y][own][max+1];
	int sum=0,tmp=0;
	if(x==n&&y==m) //     
	{
		if(own==k||own==k-1&&values[x][y]>max)
		{
			State[x][y][own][max+1] = 1;
		}
		else State[x][y][own][max+1] = 0;
		return State[x][y][own][max+1];
	}
	else
	{
		//                  max，       ，             
		if(values[x][y]>max)
		{
			tmp = values[x][y];
			if(x+1<=n)
				sum = (sum+search(x+1,y,own+1,tmp))MOD;
			if(y+1<=m)
				sum = (sum+search(x,y+1,own+1,tmp))MOD;
		}
		if(x+1<=n) sum = (sum+search(x+1,y,own,max))MOD;
		if(y+1<=m) sum = (sum+search(x,y+1,own,max))MOD;
		State[x][y][own][max+1] = sum;
		return sum;
	}
}