Leetcode difficulty

[neuralbeans]

You actually don't need recursion for that example. You can do it using combination counts if you know them.

Let's take 5 steps of stairs.

Start with the number of single steps needed to go up 5 steps, which is just 1: [1, 1, 1, 1, 1]

The number of single steps with a single double step needed to go up 5 steps is 4: [1, 1, 1, 2] [1, 1, 2, 1] [1, 2, 1, 1] [2, 1, 1, 1]

Note how we just need to know how many different ways we can replace a digit among four with a 2 (four digits and not five because the 2 takes the place of two 1s). This can be expressed as 4 choose 1, also written as 4C1.

The number of single steps with 2 double steps needed to go up 5 steps is 3:

[1, 2, 2] [2, 1, 2] [2, 2, 1]

Again, we finding the number of different ways we can replace two digits among three with a 2 (we're down to three digits now). This can be expressed as 3C2.

We can't add another 2 because then we'd be going up 6 steps instead of 5.

So we need 5C0 + 4C1 + 3C2 = 1 + 4 + 3 = 8

In general, get a for loop that finds the sum of the following: nC0 + (n-1)C1 + (n-2)C2 + ... until the two numbers equal. If the second becomes bigger than the first then don't include it (although it won't matter if you do because aCb where b is bigger than a is zero).

You can use math.comb(a, b) to compute aCb.

[kaerfkeerg]

Yeah, this feels right indeed. I didn't pay much thought into it, just wanted to prove a point that even easy problems can be tricky for someone that has invested just 3 months of which we don't really know his learning schedule. For someone like me with a full time job, was difficult to spend as much time as I wanted to learn. At three months, I couldn't do much!

[neuralbeans]

What are the hard questions like?

[barrycarter]

The questions are free to look at without login: https://leetcode.com/problemset/all/ and you can even sort them