Okay, here is another freebie.
This problem was asked by Amazon.
There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.
For example, if N is 4, then there are 5 unique ways:
1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2
What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.
Octave solution
This implementation uses memoization, resulting in a space complexity linear in K and time complexity linear in K*|X| for some K between 1 and N inclusive.
function count = step_orders(distance, permissible_steps = [1, 2])
memos = sparse(distance, 1);
hits = (memos ~= 0);
count = step_orders_stateful(distance);
function sub_count = step_orders_stateful(sub_distance)
sub_count = 0;
for first_step = permissible_steps
remainder = sub_distance - first_step;
if remainder > 0
if ~hits(remainder)
memos(remainder) = step_orders_stateful(remainder);
hits(remainder) = true; end;
sub_count += memos(remainder);
elseif remainder == 0
sub_count += 1; end; end; end; end;
