0w1

HR Grid Walking ( DP )

https://www.hackerrank.com/challenges/grid-walking
We should first determine the number of paths with some particular number of moves on each dimension separately, let's have wdm[ i ][ j ] = number of paths on dimension i, with length j. Then, consider dp:
dp[ i ][ j ] : number of paths with length j, after examining the first i dimensions
{ \displaystyle
dp( i, j ) = \sum_{k=0}^{j} dp( i - 1, k ) * wdm( i - 1, j - k ) * C( j, k )
}
where C( j, k ) is the number of ways to choose k positions among j.
Note: 0 - indexed

#include <bits/stdc++.h>
using namespace std;
const int MAXT = 10 + 2;
const int MAXN = 10 + 2;
const int MAXM = 300 + 2;
const int MAXD = 100 + 2;
const int MOD = 1e9 + 7;

int T;
int N, M;
int X[ MAXN ];
int D[ MAXN ];

int C[ MAXM ][ MAXM ];

int ways_dim_move[ MAXN ][ MAXM ]; // number of ways for particular i'th dimension, having j moves
int dp[ MAXN ][ MAXM ]; // number of ways examining first i dimensions, with length of j moves

void solve(){
    memset( ways_dim_move, 0, sizeof( ways_dim_move ) );
    for( int i = 0; i < N; ++i ){
        vector< vector< int > > tdp( M + 1, vector< int >( D[ i ] + 2 ) ); // number of ways to particular cell, on dimension i
        ways_dim_move[ i ][ 0 ] = tdp[ 0 ][ X[ i ] ] = 1;
        for( int j = 1; j <= M; ++j ){
            for( int k = 1; k <= D[ i ]; ++k )
                ( tdp[ j ][ k + 1 ] += tdp[ j - 1 ][ k ] ) %= MOD,
                ( tdp[ j ][ k - 1 ] += tdp[ j - 1 ][ k ] ) %= MOD;
            for( int k = 1; k <= D[ i ]; ++k )
                ( ways_dim_move[ i ][ j ] += tdp[ j ][ k ] ) %= MOD;
        }
    }
    memset( dp, 0, sizeof( dp ) );
    for( int i = 0; i <= N; ++i )
        dp[ i ][ 0 ] = 1;
    for( int i = 0; i < N; ++i ){
        for( int j = 1; j <= M; ++j )
            for( int k = 0; k <= j; ++k )
                ( dp[ i + 1 ][ j ] += 1LL * dp[ i ][ k ] * ways_dim_move[ i ][ j - k ] % MOD * C[ j ][ k ] % MOD ) %= MOD;
    }
    printf( "%d\n", dp[ N ][ M ] );
}

int main(){
    C[ 0 ][ 0 ] = 1;
    for( int i = 0; i < MAXM - 1; ++i )
        for( int j = 0; j < MAXM - 1; ++j )
            ( C[ i + 1 ][ j ] += C[ i ][ j ] ) %= MOD,
            ( C[ i + 1 ][ j + 1 ] += C[ i ][ j ] ) %= MOD;
    scanf( "%d", &T );
    for( int kase = 1; kase <= T; ++kase ){
        scanf( "%d%d", &N, &M );
        for( int i = 0; i < N; ++i )
            scanf( "%d", X + i );
        for( int i = 0; i < N; ++i )
            scanf( "%d", D + i );
        solve();
    }
    return 0;
}