[코드트리] 계단 수

문제URL : https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-stair-number/description

계단 수 설명 | 코드트리

 

 

문제 접근법 : dp 문제입니다.

dp는 되도록이면 (재귀 + 메모이제이션)top down 방식으로 푸는게 가장 쉽게 푸는방법이죠

 

즉 모든 경우의수를 전부 다 구하는 재귀를 이용해서 메모이제이션 하면됩니다.

 

소스코드 : 

#include<bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> dp;
int dfs(int cur,int before){
    if(cur==n){
        return 1;
    }
    int &cache = dp[cur][before];
    if(cache!=-1)return cache;
    int res = 0;
    if(before-1>=0)
        res= (res+dfs(cur+1,before-1))%((int)1e9+7);
    if(before+1<=9)
        res=(res+dfs(cur+1,before+1))%((int)1e9+7);
    return cache=res;
}
int main() {
    cin>>n;
    dp =vector<vector<int>>(n+1,vector<int>(10,-1));
    int res = 0 ;
    for(int i =1;i<=9;i++)
        res=(res+dfs(1,i))%((int)1e9+7);
    
    cout<<res<<"\n";
}

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.