28.) 1D- DP

1D dp questions-
1. fibonacii✅
2. climbing stairs (fibo 2.0)✅
3. frog jump✅
4. House Robber-1✅
5. House Robber-2✅

------------------------------------------------------------------------------------------------------------
How to identify a DP ques-
it involves concept of exploring all possible ways and then find the total count or the best possible way which gives min or max
-------------------------------------------------------------------------------------------------------------

Shortcut to solve a DP ques-
                                    4. find what does f(n) signifies
                                    5. write recursive soln..
                                    6. find overlapping subproblems within recursion tree.
                                    7. memoization ki feel ke liye har case pe recursion se calculation krke dekhlo
                                    8. look at parameters which are changing
                                  9. declare dp of n+1 size--> before returning update the dp--->whenver u call a                                            recursion before doing so if it exists already in the dp
                                    10. tabulation k liye recursion tree me se bottom to up ka krenge
me-
1. recursion tree banalo
2. recursive soln banao 
3. ab convert kro memoization mein, agar 0 se n mein ni hora toh n se 0 wale logic se dekho
----------------------------------------------------------------------------------------------------------------------------
1. Climbing stairs-
we will mark no. of stairs as indices
the function will return total no. of ways

Memoization-

Tabulation-












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

2.  Frog-Jump:

here, f(n-1) means min energy reqd to reach n-1 from 0th index

recursive soln-















-----------------------------------------------------------------------------------
memoization-


-------------------------------------------------------------------------------
tabulation- 

----------------------------------------------
space-optimisation:-


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

THUMB-RULE: 
whenever there is ind-1 and ind-2 in a soln of dp, there will be always space optmisation possible there...
-----------------------------------------------------------------------------------------------------------------------------
 FROG JUMPS-2

Now you can jump not only i+1 or i+2 , but upto i+k








time- O(k*n),     space- O(2n)

time- O(nk),   space-O(n)







can't space optimise to O(1)

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

MAX SUM OF NON- ADJACENTS/ HOUSE ROBBER-1

sort of dp on subseq with pick or not pick technique

for memoization we define f(n) as the max robbery we can do till index n

there are n states, so time complexity reduced to O(n)

tabulation-


---------------------------------------------
space optimisation-
time-o(n) & space-o(1)
----------------------------------------------------------------------------------------------------------------------------

 HOUSE ROBBER-2
Now houses are arranged on circle...
same as prvs ques just one extra thing now that first and last elmts are also now the adjacent elements

RECURSIVE-
MEMOIZATION-
TABULATION-
SPACE OPTIMISATION-

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

Comments

Post a Comment

Popular posts from this blog

30.) DP on subsequences

Image
Subset sum = target✅⭐ Partition equal subset sum✅ Partition array into 2 subsets with min abs [sum(v1)-sum(v2) ]✅ Count subsets with sum k✅⭐ Count partitions with given diff✅ target sum✅ 0/1 knapsack✅⭐ min coins✅---->count min coins to be taken coin change-2--->count n(ways) of taking coins⭐✅ unbounded knapsack✅ rod cutting problem✅ ----------------------------------------------------------------------------------------------------------------------------- 2 ways to generate all subsequences- Power Set, or Recursion subset means subsequence in dsa ----------------------------------------------------------------------------------------------------------------------------- 1. Target Sum- QUES- return true if there exists a subset with sum equal to the target in the array... Soln assuming all array elements are positive  here f(n-1,target) will tell if there's a subsequence till n-1 index with sum = target 1.) RECURSIVE SOLN-        ( time: 2^n    ...
Read more

19. Strings (LB)

Image
Character Array- 1. We use  1d character array  to simulate strings, e.g., char ch[10]; cin>>ch; 2. string ends with '\0' 3. cin with string works only if till space, tab or new line is absent in input... 4. work with character array just like a normal array, here only datatype is changed to char, else wise it is just an array -------------------------------------------- 5. In-Built functions- - int n = strlen(ch)   - strcmp(s1,s2)            // gives 0 if both strings are equal  - strcpy(dest,source)   // copies a string from dest to source -------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- It is a C++ STL 1. has dynamic size (can dynamically increase size when needed) 2. null terminator (\0) NOT required 3. Has built-in functions : - return s.size() - return s == "hello" - return s + "wor...
Read more

32. Binary Trees-2 (bfs/dfs med problems)

Image
Medium problems- more imp---------------------- height            ✅ diameter        ✅ max path sum✅⭐ Height Balanced BT check✅ identical BT check✅ Symmetric BT check✅⭐ medium imp------------------- Zig Zag traversal✅ Boundary Traversal✅ Vertical order Traversal✅⭐ less imp---------------------------- Top view ✅⭐ Bottom view✅ Right/ Left view✅ ----------------------------------------------------------------------------------------------------------------------------- 1. Max Depth of BT- height(tree)  =    n(nodes) in longest path from top to bottom time-N          space-N ----------------------------------------------------------------------------------------------------------------------------- 2. Balanced BT check- it means for every   node:      [ H(left) - H(right) ] <=1 Brute-          time: O(n^2) -------------------------------------------...
Read more