Problem Statement
You are given a chessboard of size N × N. There is a white knight and several black pawns located on the board. The knight can move similarly to the normal knight in the game of chess; however, it can only move towards the right of the board. The mission of the knight is to capture as many black pawns as possible. Its journey ends when it moves to the rightmost column of the board. Compute the maximum number of black pawns the white knight can capture.
Approach
The code uses a recursive function with memoization to compute the maximum number of pawns that the knight can capture starting from its initial position. It checks each valid knight move (up-left, down-left, up-right, and down-right) and accumulates the count of pawns captured ('P') while ensuring the knight remains within the grid boundaries. The dp table stores previously computed results to optimize performance and avoid redundant calculations.
Time Complexity
The time complexity is O(N^2) because each cell in the N×N grid is processed once.
Space Complexity
The space complexity is O(N^2) due to the dp table storing the results for each cell.