10844번: 쉬운 계단 수

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


$O(n)$

dp[1][1~9]=1
dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]

답은 sum(dp[n][i])

#include<cstdio>
#define mod (int)1e9
int n, dp[100][12], s;
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= 10; i++) dp[0][i] = 1;
    for (int i = 1; i < n; i++)
        for (int j = 1; j <= 10; j++) dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
    for (int i = 1; i <= 10; i++) s = (s + dp[n - 1][i]) % mod;
    printf("%d", s);
    return 0;
}