남교배-지하궁취보

폭력 검색은 시간을 초과해 기억화 검색으로 바뀌는 것이 DP다.

#include 
#include 

#define MAX 50 + 10
#define MOD 1000000007

int n, m, k;
int MGraph[MAX][MAX];
int dp[MAX][MAX][MAX][MAX];
//int ans = 0;

/*
void dfs( int curX, int curY, int curSum, int curMax ) {
    if( curX >= n || curY >= m ) return;    //   
    if( curSum > k ) return;    //   

    //         
    if( curX == n - 1 && curY == m - 1 ) {
        if( ( curSum == k ) || ( ( curSum == k - 1 ) && MGraph[curX][curY] > curMax ) )
            ans = ( ans + 1 ) % 1000000007;
        return;
    }
    //      
    if( MGraph[curX][curY] > curMax ) {
        //  
        dfs( curX + 1, curY, curSum + 1, MGraph[curX][curY] );
        dfs( curX, curY + 1, curSum + 1, MGraph[curX][curY] );
        //   
        dfs( curX + 1, curY, curSum, curMax );  //   
        dfs( curX, curY + 1, curSum, curMax );  //   
    }
    //    
    else {
        dfs( curX + 1, curY, curSum, curMax );  //   
        dfs( curX, curY + 1, curSum, curMax );  //   
    }

    if( curX + 1 < n ) {
        if( MGraph[curX][curY] > curMax ) {
            dfs( curX + 1, curY, curSum + 1, MGraph[curX][curY] );
        }
        dfs( curX + 1, curY, curSum, curMax );
    }
    if( curY + 1 < m ) {
        if( MGraph[curX][curY] > curMax ) {
            dfs( curX, curY + 1, curSum + 1, MGraph[curX][curY] );
        }
        dfs( curX, curY + 1, curSum, curMax );
    }

}
*/

int dfs( int curX, int curY, int curSum, int curMax ) {
    if( dp[curX][curY][curSum][curMax] != -1 ) {
        return dp[curX][curY][curSum][curMax];
    }

    if( curX >= n || curY >= m ) return 0;    //   
    if( curSum > k ) return 0;    //   

    //         
    if( curX == n - 1 && curY == m - 1 ) {
        if( ( curSum == k ) || ( ( curSum == k - 1 ) && MGraph[curX][curY] > curMax ) )
            return dp[curX][curY][curSum][curMax] = 1;
        return dp[curX][curY][curSum][curMax] = 0;
    }

    int t = 0;
    //      
    if( MGraph[curX][curY] > curMax ) {
        //  
        t = ( t + dfs( curX + 1, curY, curSum + 1, MGraph[curX][curY] ) ) % MOD;
        t = ( t + dfs( curX, curY + 1, curSum + 1, MGraph[curX][curY] ) ) % MOD;
        //   
        t = ( t + dfs( curX + 1, curY, curSum, curMax ) ) % MOD;  //   
        t = ( t + dfs( curX, curY + 1, curSum, curMax ) ) % MOD;  //   
    }
    //    
    else {
        t = ( t + dfs( curX + 1, curY, curSum, curMax ) ) % MOD;  //   
        t = ( t + dfs( curX, curY + 1, curSum, curMax ) ) % MOD;  //   
    }

    return dp[curX][curY][curSum][curMax] = t % MOD;
}

int main() {
    memset( dp, -1 , sizeof( dp ) );
    scanf( "%d%d%d", &n, &m, &k );

    for( int i = 0; i < n; i++ ) {
        for( int j = 0; j < m; j++ ) {
            scanf( "%d", &MGraph[i][j] );
            MGraph[i][j]++;
        }
    }

    int ans = dfs( 0, 0, 0, 0 );
    printf( "%d
", ans );
    return 0;
}