[LeetCode] 70. Climbing Stairs

轉自LeetCode

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?

<Solution>

從題意來看，i 階的走法，可以從 i-1 階來，也可以從 i-2 階來

寫成公式 : f(x) = f(x-1) + f(x-2)

這其實就是 fibonacci 數列，釐清這點，剩下就很簡單了

code 如下
c++

	class Solution {
	public:
	int climbStairs(int n) {
	int first = 1, second = 1;
	int tmp;
	while(n--) {
	tmp = second;
	second += first;
	first = tmp;
	}
	return first;
	}
	};

view raw climbingStairs.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun climbStairs(n: Int): Int {
	var first = 1
	var second = 1
	var temp: Int
	for(i in 1..n) {
	temp = second
	second += first
	first = temp
	}
	return first
	}
	}

view raw climbing_stairs.kt hosted with ❤ by GitHub