Interview Experience || Memoized && Tabulation
RECURSIVE + MEMOIZED SOLUTION :\n   let say  you are at (0,0) and somebody ask you number of ways to reach out (0,0) your answer will be 1 not 0 . because there
**RECURSIVE + MEMOIZED SOLUTION :**\n*   let say  you are at (0,0) and somebody ask you number of ways to reach out (0,0) your answer will be 1 not 0 . because there is 1 way to reach (0,0) which is dont make any move . [this is going to help us in thinking base case]\n*   You can see by making a recursion tree that calls are repeating . [In generall whenever we do make more than one recursion call calls do  repeat in almost every case].\n*   have a faith on recursion function that it will give me no of unique paths from intermediate to destination.\n*   I can go down or right . So just paas them on recursion function having faith it will bring answer from themself to destination .\n*   just add the number of unique ways from down and right this is the total no of unique ways.\n*   I have used bottom-up in my solution you can use top to bottom also.\n\n**CODE:**\n```\nclass Solution {\n    public int uniquePathsWithObstacles(int[][] obstacleGrid) {\n        \n        return paths(0,0,obstacleGrid.length-1,obstacleGrid[0].length-1,obstacleGrid,new int[obstacleGrid.length][obstacleGrid[0].length]);\n    }\n\t\n\t //sr:source row , sc: source column\n     //dr: destination row , dc: destination column \n\t //qb: question bank to ask question have we solved this row and col before ? if yes then why to solve again\n\t \n    public static int paths(int sr,int sc,int dr,int dc,int[][] grid,int[][] qb){\n        if(sr==dr && sc==dc && grid[sr][sc]==0) return 1;\n        \n        if(sr>dr || sc>dc || grid[sr][sc]==1) return 0; // if \n\t\t\n        if(qb[sr][sc]!=0) return qb[sr][sc];\n\t\t\n        int iv=paths(sr+1,sc,dr,dc,grid,qb); //iv: intermediate vertical\n        int ih=paths(sr,sc+1,dr,dc,grid,qb); // intermediate horizontal\n        \n        int tp=iv+ ih; //tp: total path\n        qb[sr][sc]=tp;\n        return tp;\n    }\n}\n```\n\n**Complexity:**\n`Time:O(n^2) and Space:O(n^2)`\n\n**Iterative [Tabulation] :**\n* I am Starting from dr,dc and building the answer. \n* First solve those (r,c) whom you are going to use to get your answer. \n**CODE:**\n```\n public int uniquePathsWithObstacles(int[][] obstacleGrid) {\n          int[][] dp=new int[obstacleGrid.length][obstacleGrid[0].length];\n           \n           int dr=dp.length-1;\n           int dc=dp[0].length-1;\n        \n          for(int r=dr;r>=0;r--){\n            for(int c=dc;c>=0;c--){\n                int rp1=r+1;  //rp1: row plus 1\n                int cp1=c+1; //cp1 : col plus 1\n                \n                if(obstacleGrid[r][c]==1){  //if obstacle means block\n                    dp[r][c]=0;\n                }else if(r==dr && c==dc){\n                     dp[r][c]=1;  // if i am at dr,dc number of ways =1 dont make any move\n                }else if(r==dr){\n                     dp[r][c]=dp[r][cp1];  // last row means can move only horizontal vertical moves are not valid\n                }else if(c==dc){\n                      dp[r][c]=dp[rp1][c];\n                }else{\n                    dp[r][c]=dp[rp1][c] + dp[r][cp1];\n                }\n            }  \n          }\n        return dp[0][0];\n    }\n```\n\n**Complexity:**\n`Time:O(n^2) and Space:O(n^2)`\n\n\n\n**Interview Experience:**\nI have got this  question at UNDOSTRES final interview. My final interview went for 4 hours but unluckily 0 selection from our college this time maybe because of Covid. This was my 1st International Interview . Those who dont know about undostres its like paytm in MEXICO. They only hire for MEXICO location . \nwhen interviewer gave me this question dont know why but I smiled then he asked have you solved this question before . I told maybe yes not sure but i have solved similar questions. then I have wrote tabulation code and it got passed in one go. but maybe interviewer got an idea that i have solved this before so he gave another question after this.\nInterview started at 8:00 pm and  ended at 11:48 PM .\nBut It was great fun interviewing with them .Interviewer want me to give chance thats why he strecthed interview so much .\n\nPlease **UPVOTE** if found it helpful and feel free to reach out to me or comment down if you have any doubt.\n\nI would highly recommend to follow **PEPCODING** dp Playlist on youtube if you want a expertie in this kind fo questions.
['Dynamic Programming', 'Memoization', 'Java']