ChessMetric - 2003 TCCC Round 4 - TopCoder

Dynamic Programming

I solved it in O( size*size*numMoves ). I implement an array DP[101][101][51] and what's the state of this DP problem? DP[i][j][m] means number of ways you can reach cell[i][j] in 'm' moves.

Each cell is reachable ( at most ) from 16 other cells, that means if you want to come to cell[i][j] you can reach it from other 16 cells and you are going to add the number of ways you can reach each of them and the result is number of ways you can reach cell[i][j].

At first I set DP[start[0]][start[1]][0] = 1,     that means I can reach cell[start[0]][start[1]] in zero moves in one way. So from m=0 to numMoves if DP[i][j][m] != 0 that means I can reach it from start in m moves, I choose it and update it's neighbors DP[a][b][m+1] += DP[i][j][m]

That means I can go to cell[a][b] from cell[i][j] plus one move m --->>> m+1

DP[i][j][m] = DP[i-1][j-1][m-1] + DP[i-1][j][m-1] + ..... + DP[i+2][j+1][m-1]