👀 문제
https://leetcode.com/problems/climbing-stairs/
👊 도전
1. 설계
- DP를 이용한다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
*
* @author HEESOO
*
*/
class Solution {
public int climbStairs(int n) {
if(n<4) return n;
int[] dp=new int[n+1];
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++) dp[i]=dp[i-1]+dp[i-2];
return dp[n];
}
}
3. 결과
🤟 성공 🤟
4. 설명
- DP를 이용한다
- 이렇게 노가다를 해야할 것 같은 문제는 일단 1부터 개수를 세면서 규칙을 찾아본다.
- 규칙이 있다면 DP를 쓰면 된다.
- (input, answer)이라 할 때, (1,1), (2,2), (3,3), (4,5), (5,8), (6,13), (7,21) …
- 3번째 부터는 이전 두 값의 합이 answer이라는 것을 알 수 있다.
- 따라서, dp[i]=dp[i-1]+dp[i-2]
- input이 1,2,3이면 answer==input이므로 dp를 따로 생성하지 않고 처음 if문을 통해 값을 리턴하게 했다.