백준 10844 (쉬운 계단 수)

https://www.acmicpc.net/problem/10844

점화식 dp[N][i] = dp[N-1][i-1] + dp[N-1][i+1] 이용

여기서 N 은 자릿수, i는 끝나는 수

1. 반복문

#include <iostream>
#define mod 1000000000
using namespace std;
 
int main(){
    int dp[101][10] = {};
    for(int i = 0; i < 10; i++){
        dp[1][i] = 1;
    }
    
    int N;
    cin >> N;
    
    for(int i = 2; i <=N; i++){
        for(int j = 0; j < 10; j++){
            if(j == 0) dp[i][j] = dp[i-1][1];
            else if(j == 9) dp[i][j] = dp[i-1][8];
            else dp[i][j] = dp[i-1][j-1]+ dp[i-1][j+1]; 
            dp[i][j] %=mod;
        }
    }
    
    int sum = 0;
    
    for(int i = 1; i<10; i++){
        sum=(sum+dp[N][i]) %mod;
    }
    cout << sum%mod;
}

2. 재귀

#include <iostream>
#define mod 1000000000
using namespace std;
 
int dp[101][10]={0};
 
int step(int N,int x);
 
int main(){
    int N;
    int sum = 0;
    cin >> N;
    
    for(int i =0;i<10;i++) sum = (sum+step(N,i)) % mod; 
    
    cout << sum;
    
}
 
int step(int N,int x){
    if(N==1) return x == 0 ? 0:1;
    int& ref = dp[N][x];
    if(ref) return ref;
    if(x == 0) return ref = step(N-1,1)%mod;
    if(x == 9) return ref = step(N-1,8)%mod;
    return ref = (step(N-1,x-1) + step(N-1,x+1)) %mod;
    
}