Leetcode 1269 Number of Ways to Stay in the Same Place After Some Steps

[@priyAGUPTA-kr7wb]

you are helping a lot but sometime your voice buffer so much and sound like not a ear friendly so plz improve your voice quality just a suggestion anyways you are doing great thanks for sharing :)

[@JeevanKumar-code]

Thank you for your feedback!! Will surely correct

[@shivam-codes]

I wasnt able to think of 1D dp solution so I wrote 2D dp code and converted the dp array to an unordered map and combined the 2 states to a single string in the map , and got AC. will this be a valid solution in the interview ??

[@JeevanKumar-code]

Yes this will be valid!! However if you are in a interview the interviewer will guide or direct you towards a 2d array for mem. Once you have come up with a solution that gets accepted, just think if you can make it still better. I am pretty sure if you came up with hashmap, coming up with 2d array will be very easy for you.

[@shivam-codes]

@@JeevanKumar-code initially I came up with 2D dp solution only but I got runtime as constrains for n was 10^6 and steps were 500 so my code was making a 2D array of about 5 * 10^8 size which is prohibited in c++ even if it is global array , I believe the limit is 10^7 for global arrays , hence I tried to reduce a state using map. Can this problem be solved only using 1 state i.e. steps parameter ? . I read the hint2 on leetcode for this question which said "Notice that the computational complexity does not depend of "arrlen".

[@kxrthikreddy7]

can we use recursive DP with Memoization (using a HashMap for storing values) for this problem?

[@JeevanKumar-code]

Yes, you can try that. But since all states will be visited, the hashmap will increase to same size.