Adding memorization (dp) to my recursive code gives different result which is wrong

Question

I have been stuck on this LeetCode problem Number of increasing paths in a grid:

You are given an m x n integer matrix grid, where you can move from a cell to any adjacent cell in all 4 directions.

Return the number of strictly increasing paths in the grid such that you can start from any cell and end at any cell. Since the answer may be very large, return it modulo 10⁹ + 7.

Two paths are considered different if they do not have exactly the same sequence of visited cells.

So an increasing path is defined as moving from a smaller number to a strictly increasing number, for example: 2->3->5.

I implemented this with simple recursion, but it gives a "time limit exceeded" error for the last few cases. I added two basic statements to activate dynamic programming. But when I do so, it returns the wrong results, where previously they were correct.

Code:

class Solution {
public:
    int solve(vector<vector<int>>& dp,vector<vector<int>>& grid,int i,int j,int count){
        // if(dp[i][j]!=-1)
        //     return dp[i][j];
        if((i+1)<grid.size() && grid[i+1][j]>grid[i][j])
            count=1+solve(dp,grid,i+1,j,count);
        if((j+1)<grid[0].size() && grid[i][j+1]>grid[i][j])
            count=1+solve(dp,grid,i,j+1,count);
        if((i-1)>=0 && grid[i-1][j]>grid[i][j])
            count=1+solve(dp,grid,i-1,j,count);
        if((j-1)>=0 && grid[i][j-1]>grid[i][j])
            count=1+solve(dp,grid,i,j-1,count);
        return dp[i][j]=count;
    }
    int countPaths(vector<vector<int>>& grid) {
        long long ans=0;
        vector<vector<int>>dp(grid.size()+1,vector<int>(grid[0].size()+1,-1));
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                ans=ans+solve(dp,grid,i,j,1);
            }
        }
        return ans%1000000007;
    }
};

With the code left in comments, I get correct results (when the time limit is not reached), but when I uncomment the commented statements then it gives wrong results.

What am I missing here?

Answer 1

The problem is that your count is cumulative, and so it cannot serve for memoization. Such a count includes the results of all previous traversals through the grid, and does not represent a count that is specific to a given pair of coordinates.

So if a cell is visited quite late in the process (like when it is in the bottom right corner), count will not start with 1, as it will already have counted numerous other paths that don't involve this new cell. To that count are now added the paths that start in this new cell, but the result is not representative of that cell on its own, so if on a second visit you return that count from memoization, you'll have double counted many unrelated paths.

The solution is to use a local count: a count that starts from 0 each time you start from a certain cell. The sum of these independent counts will still be your answer, but now you can use the count for memoization.

Unrelated, but your code has another problem: for large inputs you will overrun the long long capacity of your count variable. You should apply the modulo operator repeatedly, to keep the count within bounds.

In case you cannot make it work, here is a correction to your code as a spoiler:

class Solution { public: int solve(vector<vector>& dp,vector<vector>& grid,int i,int j){ if(dp[i][j]!=-1) { return dp[i][j]; } int count = 1; if((i+1)<grid.size() && grid[i+1][j]>grid[i][j]) count += solve(dp,grid,i+1,j); if((j+1)<grid[0].size() && grid[i][j+1]>grid[i][j]) count += solve(dp,grid,i,j+1); if((i-1)>=0 && grid[i-1][j]>grid[i][j]) count += solve(dp,grid,i-1,j); if((j-1)>=0 && grid[i][j-1]>grid[i][j]) count += solve(dp,grid,i,j-1); return dp[i][j] = count % 1000000007; } int countPaths(vector<vector>& grid) { int ans=0; vector<vector>dp(grid.size()+1,vector(grid[0].size()+1,-1)); for(int i=0;i<grid.size();i++){ for(int j=0;j<grid[0].size();j++){ ans = (ans + solve(dp,grid,i,j)) % 1000000007; } } return ans; } };