Maximum Number of Moves in a Grid | Recursion | DP | Leetcode 2684

This video explains finding the maximum number of moves in a grid using the most intuitive and optimal recursion and memoization with dynamic programming technique.
----------------------------------------------------------------------------------------------------------------------------------------------------------------
🟣 JOIN our 𝐋𝐈𝐕𝐄 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐭𝐫𝐚𝐢𝐧𝐢𝐧𝐠 𝐩𝐫𝐨𝐠𝐫𝐚𝐦 through whatsapp query: [phone]
---------------------------------------------------------------------------------------------------------------------------------------------------------------

[luvsharma]

it is little bit simlar question like longest square streak which you have uploaded sir

[kgjr.]

sir just a suggestion but insted of solving and explaining the problem in the way where we will get the solution can you make it in the way that we can get the intution of how can we comeUp with those solution my our self like how the neetcode explains the solutions. Also you look very serious and not happy try to enjoy the process of problem solving.

[alessandrocamilleri]

Thanks for the great explanation. This is my dp solution using tabulation to save on recursion stack space:

int maxMoves(vector<vector<int>>& grid)
{
int m = grid.size();
int n = grid[0].size();
int maxMoves = 0;

vector<vector<int>> dp (m, vector<int>(n, 0));
for (int i = 0; i < m; i++) dp[i][0] = 1;

vector<int> rowDelta {-1, 0, +1};

for (int i = 1; i < n; i++)
{
for (int j = 0; j < m; j++)
{
for (int r = 0; r < 3; r++)
{
int checkRow = j + rowDelta[r];
if (checkRow >= 0 && checkRow < m && grid[checkRow ][i-1] < grid[j][i] && dp[checkRow][i-1] == 1)
{
dp[j][i] = 1;
maxMoves = i;
}
}
}
}
return maxMoves;
}

[praveenabandari]

Not all test cases are passing, Time limit exceeded.