LeetCode Climbing Stairs再帰解と動的計画法

Climbing Stairs
 
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
簡単な問題はfibonacci数列問題に相当し、難点は思考の転換を行い、再帰的に問題を解くことに転換し、多くの訓練をすればよい.
だからこのようなタイプの問題は再帰的な論理的思考を形成していない人にとって、難題であるべきだ.
私の考えは
毎回2つの選択があり、2つの選択の後にはそれぞれ2つの選択があり、このような循環は、ちょうど再帰的な解の問題である.
再帰プログラムを書くのは簡単です.3つの文でいいです.

int climbStairsRecur(int n) {
		if (n == 1) return 1;
		if (n == 2) return 2;
		return climbStairsRecur(n-1) + climbStairsRecur(n-2);
	}

しかし、再帰プログラムは一般的に遅すぎます.Fibonacci問題のように、多くの分岐を繰り返し計算しているので、ダイナミックプランニング法を使用して表を記入し、効率を高め、プログラムも簡単です.以下のようにします.

int climbStairs(int n)
	{
		vector res(n+1);
		res[0] = 1;
		res[1] = 1;
		for (int i = 2; i <= n; i++)
		{
			res[i] = res[i-1] + res[i-2];
		}
		return res[n];
	}

動的計画法は使い慣れているので、達人は空間を節約する必要があります.以下のようにします.

int climbStairs2(int n)
	{
		vector res(3);
		res[0] = 1;
		res[1] = 1;
		for (int i = 2; i <= n; i++)
		{
			res[i%3] = res[(i-1)%3] + res[(i-2)%3];
		}
		return res[n%3];
	}

もちろん,上の配列を用いなくてもよいが,直接3つの変数を用いて結果を保存しても同様である.

//2014-2-10 update
	int climbStairs(int n)
	{
		if (n < 4) return n;
		int a = 2, b = 3, c = 5;
		for (int i = 5; i <= n; i++)
		{
			a = c;
			c = b+c;
			b = a;
		}
		return c;
	}