Easy || Recursion || Optimizing Recursion using Memoization
\n#### RECURSION\n  For every (i, j), there are two possibilites of movement : DOWN (i+1, j) & RIGHT (i, j+1)\n\n INVALID BASE CASES:\n\t1. \tIf index i or inde
\n#### **RECURSION**\n*  For every (i, j), there are two possibilites of movement : DOWN (i+1, j) & RIGHT (i, j+1)\n\n* **INVALID BASE CASES:**\n\t1. \tIf index i or index j is out of bounds.\n\t\n\t2. \tIf (i, j) cell has an obstacle.\n\t\n\t\t***In all these cases, the number of unique paths is 0.***\n\t\n*  **VALID BASE CASE:**\n      \n\t1. If (i, j) cell is our destination cell(m-1, n-1), \n\t\n\t      ***The number of unique path is 1.***\n\t\n\n\nUnique paths for Down Move = func(i+1, j) \nUnique paths for Right Move = func(i, j+1)\n\t\t\t***Total unique paths = Down Moves + Right Moves = func(i+1, j) + func(i, j+1)***\n\n\n```\n class Solution {\n    int m,n;\n    int[][] grid;\n    public int recurse(int i, int j) {\n        if(i==m || j==n || grid[i][j]==1)\n            return 0; // Invalid case\n        if(m-1==i && j==n-1)\n            return 1; //Valid case\n        return recurse(i, j+1)+recurse(i+1, j);\n    }\n    public int uniquePathsWithObstacles(int[][] obstacleGrid) {\n        m = obstacleGrid.length;\n        n = obstacleGrid[0].length;\n        grid = obstacleGrid;\n        return recurse(0, 0);\n    }\n}\n```\nThis will have exponential time complexity. \n\n#### **Optimization using Memoization (Top-Down)**\nThere are many cells for which the value is computed more than once.\n\nSo, after the value for a certain cell (i, j) is computed, we can store the value and return that value later on.\n\n```\nclass Solution {\n    Integer dp[][];\n    int m,n;\n    int[][] grid;\n    public int recurse(int i, int j) {\n        if(i == m || j == n || grid[i][j] == 1)\n            return 0;\n\t\tif(dp[i][j] != null)\n            return dp[i][j]; //return the already computed value for cell (i, j)\n        if(m-1 == i && j == n-1)\n            return dp[i][j] = 1;\n        return dp[i][j] = recurse(i, j+1) + recurse(i+1, j); //store value for cell (i, j)\n    }\n    public int uniquePathsWithObstacles(int[][] obstacleGrid) {\n        m = obstacleGrid.length;\n        n = obstacleGrid[0].length;\n        grid = obstacleGrid;\n        dp = new Integer[m][n];\n        return recurse(0, 0);\n    }\n}
['Dynamic Programming', 'Recursion', 'Memoization', 'Java']