Amazon Coding Interview Question - Recursive Staircase Problem

Amazon coding interview question and answer - recursive staircase problem! For daily coding problems like this one, I’d recommend this website called Daily Coding Problem. You can find it here: https://csdojo.io/daily (That’s a referral link, and you can get a 10% discount through that link. Their free option and blog articles are good, too, though.) Outline (check my comment for the clickable outline): 0:07: Problem description 1:14: A variation of the problem 2:15: Thinking about simple cases 4:18: Finding a pattern 5:24: Relabeling the steps 6:41: Revisiting the pattern with the new labels 7:53: The pattern we’ve found - recap. 8:11: The recursive relationship we’ve found 8:50: What about when N = 0? 9:40: Writing a naive recursive solution 10:39: Why this solution is not efficient 11:24: How to fix it with dynamic programming (bottom-up) 12:27: The bottom-up solution in code 13:34: How to make it more efficient in terms of space 14:19: Solution to the variation of the problem 14:49: The recursive relationship for this problem (the variation) 15:08: A naive, INCORRECT recursive solution to this problem 15:50: A naive, CORRECT recursive solution to this problem 16:17: A naive, correct recursive solution in code 17:11: A dynamic programming / bottom-up approach 19:17: How to get daily coding problems like this one (go to https://csdojo.io/daily) Also, keep in touch on Facebook: https://www.facebook.com/entercsdojo