LeetCode 82 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?
분석:
계단을 오르는 문제는 가장 간단한 동규 문제에 속한다.
자 문제: i급 계단을 오르는 몇 가지 방법이 있습니다. dp[i],
상태 전환 방정식:
두 가지 상태 이동 방식이 있기 때문에 우리는 이 두 가지 이동 방식이 어떻게 조합되어 전환되는지 본다. 이 문제는 덧붙이는 방식이다.
dp[i] = dp[i-1] + dp[i-2]
public class Solution {
    public int climbStairs(int n) {
        //         
        if(n==0 || n==1 || n==2)
            return n;
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        for(int i=2; i<n; i++)
            dp[i] = dp[i-1] + dp[i-2];
        return dp[n-1];
    }
}

좋은 웹페이지 즐겨찾기