garote: (Default)
[personal profile] garote

This is a classic "dynamic programming" problem that job applicants in the software industry are sometimes given. The problem is this:

Given a staircase with n steps, how many different ways can you climb it, assuming that your stride is large enough to take steps 1, 2, or 3 at a time?

The solution that people pursue most easily is the recursive solution, looking something like this:

var steps = 14;
var solution = possibilities(steps, 1) +
			possibilities(steps, 2) + possibilities(steps, 3);

function possibilities(remaining, thisStride) {
	remaining -= thisStride;
	if (remaining < 0) { return 0; }
	if (remaining == 0) { return 1; }
	return possibilities(remaining, 1) +
		possibilities(remaining, 2) + possibilities(remaining, 3);
}

(This is JavaScript by the way.)

But, there is another way to find the answer, that runs in linear time -- that is, for a given value of n, the program takes around n iterations to find the answer. It involves keeping track of the last several values calculated in the loop, and it looks something like this:

var steps = 14;
var solution = stepCombinations(steps);

function stepCombinations(g) {
	var pattern = [-1,0,0,1];
	if (g < 1) { return 0; }
	var iter = 0;
	var total = 0;
	while (iter < g) {
		total = (total * 2) - (pattern[iter % 4]);
		pattern[iter % 4] = total;
		iter++;
	}
	return total;
}

The ten dollar question is: Why does this second method work?

(will be screened)
(will be screened if not validated)
If you don't have an account you can create one now.
HTML doesn't work in the subject.
More info about formatting

Profile

garote: (Default)
garote

July 2025

S M T W T F S
   12 345
6 789101112
13141516171819
20212223242526
2728293031  

Most Popular Tags

Page generated Jul. 20th, 2025 04:03 am