Beginner Friendly "Recursion to DP" Intuition Explained [Python]
Here, we have an obstacleGrid (say obs) of size m n. We can traverse through this grid by going down and/or right only.\nIdea: We start travering the array from
Here, we have an obstacleGrid (say ***obs***) of size m* n. We can traverse through this grid by going down and/or right only.\n**Idea:** We start travering the array from` start index (0, 0)`.\n* We consider a `path to be valid`, if it has reached the last index (m-1, n-1).\n* We consider a `path to be invalid`, if either it exceeds the boundary of the ***obs*** grid or the current position in the ***obs*** grid has an obstacle in it.\n\nThe above two conditions serves as the **base condition of our recursion**, \n* for **valid** cases we `return 1` saying that consider this path, and \n* for **invalid** cases we `return 0` saying that do not consider this path.\n\nNow coming to **the recursive part**: We want to traverse the matrix in both right and down direction. So, we recursively call this function for both the right `(i + 1, j)` and down `(i, j+1)` indices. \n\n***How does this work?***\n\nSee consider you are currently at any arbitrary index in the matrix `(i, j)` . Your goal is to return the `max number of valid paths from (i, j) to (m-1, n-1)`.\n\n`From (m-1, n-1) to (m-1, n-1)`, we have just one valid path so return 1 directly from the base condition.\n...\n`From (i, j) to (m-1, n-1)`, let us assume there was **1** possible path to go from the downside and **1** possible path to go from the rightside, so total number of ways to reach (m-1, n-1) from (i, j) becomes 1 + 1 **= 2**. \n\nIn general, if there was **x** possible path to go from the downside and **y** possible path to go from the rightside, so total number of ways to reach (m-1, n-1) from (i, j) becomes **x + y**.\n\nSimilarly, If we compute it for index (0, 0) to (m-1, n-1), we will get all possible ways to reach from start index to the end index.\n\nThe recursive code (***not working, TLE***) is given below:\n\n```\nclass Solution:\n    \n    # here I just changed the formal variable name \n    # from obstacleGrid to obs just for convinience\n    \n    def uniquePathsWithObstacles(self, obs: List[List[int]]) -> int:\n        m, n = len(obs), len(obs[0])\n        \n        def solve(i , j):\n            # base condition for recursion\n            if i == m - 1 and j == n - 1:\n                return 1\n            if i >= m or j >= n or obs[i][j] == 1:\n                return 0\n            # the down and right recursive calls respectively\n            return solve(i + 1, j) + solve(i, j+1)\n        \n        return solve(0,0)\n```\n\nNo doubt, the above solution runs perfectly fine. But it doesnot match the expected time complexity, hence results in generating a TLE error. \n\n***Why TLE?*** =>Here there are total **m * n** grids and each having **2** possiblities : has obstacles or clear path (does not have a obstacle). We will be recursively traversing through the grid considering both the possibilites. Hence, time complexity = O(2 ^ (m * n)) = O(2 ^ (100 * 100)) = O(2 ^ 10000) = O(10 ^12) nearly.\n\nThus, **time complexity > O(10 ^ 8)**. and hence ***Time Limit Exceeded*** as Python generally caps the complexity at O(10^8), meaning you cannot exceed it. \n\n**Can we do any better?** \n\nSee generally when you have TLE for recursive solutions, you can always memoize it (it\'s just a random observation). But this is not a good reason to say to the interviewers. xD\n\n**How to identify a DP problem?** Analyze the problem and Check for overlapping subproblems, so that we can memoize it.\n\nConsider the first example as shown below: (indexes of each element is given in *(i, j)* format).\n![image](https://assets.leetcode.com/users/images/f366ba68-adf7-4e50-9667-49190b5a86e4_1653007809.711647.png)\n\nLet\'s say we are at (0, 1), so by our recursive apporach we would calculate the value of (1,1) , i.e., down and (0, 2), i.e., right indices.\nNow, let\'s say we reached (1, 0), here also we will need to calulate (2, 0) and (1, 1). \n\nBut haven\'t we already calulated the number of paths for (1, 1) earlier? **Yes, we did** right (when we were traversing down from (0, 1) index). \n\nSo, why not **store it some where** so that we can use it later without the need of recomputing it.\nJust store the previously computed value and return it whenever the (already computed) index (1, 0) is called. Similarly, do the same for all indices that requires recomputation.\n\nThis process of finding overlapping subproblems, storing the computed value, reusing the previously computed value and reducing the recomputation complexity is called **Memoization** or **Top Down Dynamic Programming Approach** (this is specific to recursion, it\'s nearly equivalent *Bottom up approach or Tabulation* is achieved using iteration).\n\nThe Memoized Code: (**Top Down DP**) => **ACCEPTED**.\n```\nclass Solution:\n    \n    # here I just changed the formal variable name \n    # from obstacleGrid to obs just for convinience\n    \n    def uniquePathsWithObstacles(self, obs: List[List[int]]) -> int:\n        m, n = len(obs), len(obs[0])\n        \n        # create a dp array of size m * n to store already computed number of paths for index (i, j) to end\n        # where 0 <= i < m and 0 <= j < n\n        # initialize the dp array by -1 as number of paths can only be a whole number.\n        dp = [[-1]*n for _ in range(m)]\n        \n        def solve(i , j):\n            if i >= m or j >= n or obs[i][j] == 1:\n                return 0\n            \n            if i == m - 1 and j == n - 1:\n                return 1\n            \n            \n            # if the value of dp[i][j] is updated then directly return the updated value\n            if dp[i][j] != -1:\n                return dp[i][j]\n            \n            # else compute the value of dp[i][j] for the first time ever\n            # and return it saying that the returned number (dp[i][j]) of ways are possible from\n            # (i, j) to the end index.\n            dp[i][j] = solve(i + 1, j) + solve(i, j+1)\n            return dp[i][j]\n        \n        return solve(0,0)\n```\n\n**Time and Space Complexity Analysis:** (for Top Down DP)\nHere, each of the successful recursive calls (whose value will be inserted in the dp matrix) will exactly be called once, because later it will take it directly from the dp array in constant time. And the unsuccessful recursive calls will return from the base condition in constant time. But we are traversing through the matrix of size \'m * n\' through nested loops (simultaneously). Thus, **optimized time complexity = O(m * n)** owing to the traversal of matrix.\n\nNow, we have used only one variable sized space that is dp array of size \'m * n\'. Apart from that all other variables are constant sized like n, m, ans, etc.. are fixed sized 32 - bit integer variables. So, no need to consider that, as their size will always be fixed and will not change with respect to change in input variable. Hence, **Space complexity = O(m * n)** owing to the dp array.\n\nNow, we know that, any code that is written in **Top Down DP can be easlily converted to Bottom-up DP**. \n\n**Is there any advantage of doing so?** or Is it just a waste of time to convert the recursive code to Iterative code?\n\nSee, whenever there is recursion involved we use some extra memory in the stack region of the main memory (RAM) to store the functions that are being called recursively one after another.\n\nThis stack space is not considered while calculating the output space complexity. So, **asymptotically, it does not** matter whether you convert recursion into iteration or not. But **practically it does matter**.\n\n***Let\'s see how*** => The max depth of recursion will be O(m + n) as in the worst case **either** we will go fully towards right then fully towards down **or** we will first go fully towards down then move straight fully to the right, till we reach the end index. (It will not be anything more than O(m + n)) as we do not traverse back (i.e., top or left) ever. \n\nHence **Stack Space =** max number of recursive functions called at a stretch = max depth of recursion **= O(m + n)**. \n\nThus, by coverting the Top Down DP to Bottom Up DP, we can further reduce this practical execution space. Thus, keeping our main memory little bit free for storing other data, hence reduing page faults (ignore it for now, if you don\'t know).\n\nThe Tabulation Method (**Bottom Up Dp**): => Definitely **accepted**..... xD\n```\nclass Solution:\n    \n    # here I just changed the formal variable name \n    # from obstacleGrid to obs just for convinience\n    \n    def uniquePathsWithObstacles(self, obs: List[List[int]]) -> int:\n        m, n = len(obs), len(obs[0])\n        \n        # create a dp array of size m * n to store already computed number of paths for index (i, j) to end\n        # where 0 <= i < m and 0 <= j < n\n        # initialize the dp array by -1 as number of paths can only be a whole number.\n        dp = [[0]*n for _ in range(m)]\n        \n        if obs[0][0] == 1 or obs[-1][-1] == 1:\n            return 0\n        \n        # initialize the first row first column of dp\n        # assign the clear path = 1 and obstacles = 0 value in dp based in obstacle_grid\n        # we did this because we want to add clear paths and not add obstacles path.\n        dp[0][0] = 1\n        for i in range(1,m):\n            dp[i][0] = 1 if obs[i][0]==0 and dp[i-1][0]==1 else 0\n            \n        for j in range(1,n):\n            dp[0][j] = 1 if obs[0][j]==0  and dp[0][j-1]==1 else 0\n        \n        # add clear paths if no obstacles are found.\n        for i in range(1, m):\n            for j in range(1, n):\n                if obs[i][j] == 0:\n                    dp[i][j] = dp[i-1][j] + dp[i][j-1]\n        print(dp)\n        return dp[m-1][n-1]\n```\n\nI am leaving the above code for you to understand yourself as it will help you analyze deeper. For hints, I have given a few comments in the code.\n\nAlso, **note that** in Top Down DP we returned dp[0][0] but in Bottom Up DP Approach we returned dp[-1][-1]. Why??? - Brainstorm a little first, and do comment down below, your findings regrading this.\n\nTime Complexity = Space Complexity = O(m * n)  for Bottom Up DP (in this case).\n***Can we further reduce the space complexity?*** Yes, we can use the obstacle grid itself inplace of DP array to reduce the space complexity to O(1). But generally, modfying the input itself is not considered a wise choice, until and unless an inplace solution is required, where you do not need to return anything, just modify the input array as per conditions and the main function will access it using reference of the input variable. So, no need to return. Hence, inplace. But when nothing such is mentioned and, in real life scenerio if we modify our input array, there might be a possiblilty that this array may be used further somewhere in the program. But by modifying it, we lost the original array, which may not be a good practice.\n\nIf this helps you, then **Please UPVOTE**.\n\n***Similar Problems with detailed intuitions explained:***\n\n* *Leetcode 329. Longest Increasing Path in a Matrix: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/discuss/2052360/python-beginner-friendly-recursion-to-dp-intuition-explained*\n\n* *Leetcode 576. Out of Boundary Paths: https://leetcode.com/problems/out-of-boundary-paths/discuss/1293697/python-easy-to-understand-explanation-recursion-and-memoization-with-time-and-space-complexity*\n\n* *Leetcode 792. Number of Matching Subsequences: https://leetcode.com/problems/number-of-matching-subsequences/discuss/1289549/python-explained-all-possible-solutions-with-time-and-space-complexity*
[]