백준 10844 :쉬운 계단 수

#include <iostream>
#include <algorithm>

using namespace std;

int dp[101][10];
  
int main(void)
{
int n;
int sum = 0;

cin >> n;

for (int i = 0; i < 10; i++)
dp[1][i] = 1;
for (int i = 2; i <= n; i++)
{
for (int j = 0; j < 10; j++)
{
if (j == 0)
dp[i][0] = dp[i - 1][1];
else if (j == 9)
dp[i][9] = dp[i - 1][8];
else
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
}
}

//for (int i = 0; i < 10; i++) {
// for (int j = 0; j < 10; j++) {
// cout << dp[i][j] << ' ';
// }
// cout << endl;
//}
for (int i = 1; i < 10; i++)
sum = (sum + dp[n][i]) % 1000000000;

cout << sum % 1000000000;
}

n이 1일땐 1~9까지 9개이고
n이 2부터는 2는 1과 3 , 3은 2 와 4 두 가지로 퍼져나갈 수 있지만
0에서는 1, 9는 8로 1가지 밖에 퍼져나가지 않는다. 

if (j == 0)
dp[i][0] = dp[i - 1][1];
else if (j == 9)
dp[i][9] = dp[i - 1][8];
else
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
그래서 점화식을 이렇게 세워주면 된다.