29.) 2D-dp, dp on grids, 3D-dp

TOPICS-

• ninja's training✅
• count all unique paths✅
• count paths with obstacles✅
• min path sum/                   fix st & fix end pts✅
• min path sum in triangle/ fix st & var end pt✅
• falling path sum /             var st & end pts✅
• ninja & frnds/ 3d dp/       fix st & var end pts⭐✅

-----------------------------------------------------------------------------------------------------------

top down means top guy in recursion tree will get answer by going down

bottom up means bottom guy will get answer by going up, or you start from the base case and accumulate all the stuff till top and get the answer

------------------------------------------------------------------------------------------------------------

recursive soln building-

1. write everything in index form

2. do all stuffs on that index

3. find way to get best/ optimal answer

------------------------

memoization-

1. initialize dp array 

2. return wali line mein dp mein store krlo saath ki saath

3. jis loop mein recursive fn call hora usse pehle dp mein agar vo soln already exist krta hai vo check ki condition lagado

------------------

Tabulation-

1. declare base cases of dp array

2. express all states in the form of for loops

3. copy recurrence and write

-----------------------------------------------------------------------------------

 1. Ninja's Training-

state- f(idx,x)  means max points from 0 to idx day given that last day(idx+1) did x task

 we will use day no. as our index and the info about what task we did on the last day

we can pass last task as 3 when starting so as to try out all the tasks

f(x,y) here means that on day x, we can perform any task other than task y

base case- starting from n-1)th day, our base case is what if ind we are at is 0 

transition- it is similar to base case just that for the points part we will add ith day's best task and leave rest of the max points possible from rest of the array on the recursive fn

---------------------------------------

Recursive soln- 

--------------------------------------------------------------

MEMOIZATION-

since there are overlapping sub problems, so we can have a memoization solution

for every state (day) there are 4 different choices to be taken as the changing parameter

so we need a Nx4 sized dp array

also we can see since there are 2 changing parameters so we need a 2d dp array

time- O(Nx4x3)                space- O(N)+O(Nx4)

-------------------------------------------------------

TABULATION-

time- (Nx4)x3        space- (Nx4)

----------------------------------------

SPACE OPTIMISATION- 

space- O(1)

instead of a matrix which needs last day values for current day, we can instead make a dummy array of size 4 and update it after each row

------------------------------------------------------------------------------------------------------------

2. Grid Unique Paths-1

me-

----------------------------------------------------------------------

striver-

recursive soln-    time: 2^(mn)     space: (m-1)+(n-1)

memoized soln-     time: (mn)    space:(m-1)+(n-1)+nm

Tabulation-  time: nm        space:nm

SPACE OPTIMISATION-

since for an element in a row, we just need a guy to its left and a guy above it , so need not require extra rows above it, we can only have a temp row above the current row from where we can fetch prvs rev values...thus we can space optimise it

-------------------------------------------------------------------------------------------------------------------------

3. Grid paths with obstacles-

just one more base case addition to prvs problem that if cell is blocked we will return 0

------------------------------------------------------------------------------------------------------------------------

4. Minimum Path Sum-⭐

simple- just that for the negative indices base case, you have to return int max since we are finding min path sum...

whenever there is non uniformity in values, we can't apply greedy algo

----------------------------------------------------------------------------------------------------------------------------

5. Minimum Path Sum in triangular grid-

fixed starting point & variable ending point

so for recursive soln we can't start from bottom, instead we will start from top

---------------------------------------

RECURSIVE SOLN-

time- exponential,    space-N(stack space)

---------------------------------------

MEMOIZED SOLN-

time- n*n        space-n + n*n

NOTE- time complexity of a memoized solution is typically equal to the number of unique states that the recursive function can be called with.

---------------------------------------

TABULATION SOLN-

time: n*n        space: n*n

NOTE- we can remove stack space from memoized solution, using tabulation method
           - tabulation is always opp sense of recursive soln

           - recursive soln is always top-down, no matter if u start from 0 or n-1

-------------------------------------------------------------------

SPACE OPTIMISATION-

instead of entire dp matrix, for calculating values of a current row, we just need a prvs row...

space: n

-----------------------------------------------------------------------------------------------------------------------------

6. Falling path Sum

(variable starting & ending point)

Recursive-

time: (3^n)    space: n

Memoized soln-

time: O(n^2)              space: (n^2 + n)

Tabulation:

time- O(n^2 + n)        space: (n^2)

Space optimisation-

space: (n)

----------------------------------------------------------------------------------------------------------------------------

7. Cherry Pickup -(3D: dp)⭐

here we won't do it like first alice goes and finds max and then bob goes and find max and then sum up

because there is a case where if both are at same cell then we have to just give that element to only one of them, so we must think of a solution where both of them moves simultaneously...

---------------------------

NOTE- since this is FIX starting point & VAR ending point problem, so we will start our recursive solution from fix point

NOTE- there are 2 types of base cases always- destination & out of bound, always write outer bound base case first...

NOTE- if you want to return INT_MIN / INT_MAX toh jis variable mein jaake ye add hoga usko long mein convert krlo nhi toh inki jagah 1e8 ya -1e8 jaisa bada number lelo...
---------------------------

-----------------------------------------

for each movement of alice there are 3 possibilities of bob moving to next row,

so in total there are 9 combos of paths that we have to track...

-----------------------------------------------------

recursive soln-

time: (3^n)*(3^n)        space: n

--------------------------------

memoized soln-

since here are 3 different parameters which are changing, so we will use a 3d dp

time: 9*r*c*c        space: (n*m*m)+n

------------------------------

tabulation-

time: 9*r*c*c        space:  extra stack space removed

----------------------

NOTE- space optimization reduces 1 dimension of the dp, e.g., for 1d dp we then only need 2 variables, similarly for 2d dp we only need 1 vector, similarly for 3d dp we would only need 2d vector

-----------------------

SPACE OPTIMIZATION:-

-----------------------------------------------------------------------------------------------------------