(LeetCode) 70. Climbing Stairs

문제 링크

• LeetCode

요약

• 가장 기본적인 DP 문제.

최종 §

결과

• 점화식만 잘 짜면 된다.

class Solution {
public:
	int climbStairs(int n) {
		// A(n+2) = A(n+1) + A(n)
		int buf[3];
 
		if (n == 1) {
			return 1;
		}
 
		buf[0] = 0; // A(0)
		buf[1] = 1; // A(1)
		buf[2] = 2; // A(2)
 
		for (int i = 0; i < n - 2; i++) {
			buf[0] = buf[1];
			buf[1] = buf[2];
			buf[2] = buf[0] + buf[1];
		}
 
		return buf[2];
	}
};

다른 언어 풀이 §

Go §

결과

• 이전에 Go로 작성해둔게 있어서 옮겨버리기

func climbStairs(n int) int {
	cache := make([]int, n + 1)
	cache[0] = 1
	cache[1] = 1
	for i := 2; i <= n; i++ {
		cache[i] = cache[i - 1] + cache[i - 2]
	}
	return cache[n]
}

Java §

결과

• 이전에 Java로 작성해둔게 있어서 옮겨버리기

class Solution {
	public int climbStairs(int n) {
		int[] cache = new int[n + 1];
		cache[0] = 1;
		cache[1] = 1;
 
		for (int idx = 2; idx <= n; idx++) {
			cache[idx] = cache[idx - 1] + cache[idx - 2];
		}
 
		return cache[n];
	}
}