leetcode[68] Climbing Stairs

3289 단어 LeetCode
n계단, 매번 한 걸음 또는 두 걸음 걸을 수 있으며, 모두 몇 가지 걷는 방법이 있다.
첫 번째 느낌은 n이 1일 때 1종, 2일 때 2중으로 돌아가는 것이다.다른 때는 fun(n)=fun(n-1)+fun(n-2);귀속 코드는 매우 간단하다.아래와 같다
class Solution {

public:

    int climbStairs(int n) {

        if (n == 0) return 0;

        if (n == 1) return 1;

        if (n == 2) return 2;

        else

            return climbStairs(n-1) + climbStairs(n-2);

    }

};

근데 시간 초과했어.태그 힌트 DP를 보았습니다.그래서 분당 DP로 바꿨어요.
class Solution {

public:

    int climbStairs(int n) {

        if (n == 0) return 0; 

        if (n == 1) return 1;

        if (n == 2) return 2;

        vector<int> ans(n);

        ans[0] = 1; ans[1] = 2;

        for (int i = 2; i < n; ++i)

        {

            ans[i] = ans[i-1] + ans[i-2];

        }

        return ans[n-1];

    }

};

과감한 AC.

좋은 웹페이지 즐겨찾기