Interesting Random Thought For The Day 3: Why Does This Work?

[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?

Comments

[juan_gandhi]

Magic. A similar trick works with Fibonacci. But how come it does not work for an arbitrary recursion of this kind.

[garote]

You're very much on the right track to understanding this. This is the so-called "tribonacci" sequence. It's just being iterated in a strange way. Instead of summing the previous three values, we're taking only the previous value and doubling it, and then subtracting the value from four iterations ago. The number ends up being the same.

But the deeper question is still there: Why does this work?

I think it has something to do with the way we have three choices for step strides - 1, 2, 3 - and three previous numbers. Like, perhaps the three numbers we're adding represent all the ways each type of stride can be arranged, and the first number is relatively small because the strides of 3 steps are relatively long...

But then I try to analyze it further, and my brain slips on a banana peel and tumbles to the bottom again.