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
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; }