Hello! Today we will take a closer look at one of the algorithm problems that often appears in Python coding tests, “Counting Stair Numbers”. Through this problem, we will learn the concept of dynamic programming and the process of solving problems.
Problem Description
A stair number is defined by the following rules:
- A stair number is composed of digits from 0 to 9.
- The digits of two adjacent positions must differ by exactly 1. For example, 234 is valid, but 235 or 123 are not valid.
- The first digit of a stair number cannot be 0.
Given a natural number N, how many stair numbers of length N exist? For example, if N is 2, there are 9 possible stair numbers: 10, 12, 21, 23, 32, 34, 43, 45, 54, 65, 76, 78, 87, 89, 98, totaling 15.
Input Format
The first line contains the number of digits in the stair number N (1 ≤ N ≤ 100).
Output Format
The first line should output the number of N-digit stair numbers modulo 1,000,000,000.
Example Input
2
Example Output
15
Problem Solving Strategy
This problem can be solved using dynamic programming. Stair numbers can be categorized according to the rules of the problem, and for each digit, we consider the possible number combinations to derive the results. Now, let’s look at the specific solution process.
Step 1: State Definition
To find N-digit stair numbers, we define a DP array. We use dp[n][k] to represent the number of stair numbers of length n whose last digit is k. Here, n is the number of digits, and k is the last digit (0 to 9).
Step 2: Initial Condition Setting
The stair numbers of length 1 are from 1 to 9. Therefore, we set dp[1][0] = 0 (0 cannot be the first digit), and dp[1][1] = dp[1][2] = ... = dp[1][9] = 1.
Step 3: Deriving the Recursion Formula
To construct stair numbers of length n, we add one digit to stair numbers of length n-1. If the last digit is 0, it can lead to 1, and if the last digit is 9, it can lead to 8. Therefore, we get the following recursion formulas:
dp[n][0] = dp[n-1][1] dp[n][k] = dp[n-1][k-1] + dp[n-1][k+1] (1 <= k <= 8) dp[n][9] = dp[n-1][8]
Step 4: Calculating the Final Result
The N-digit stair numbers can be found by summing up the cases for all digits from 0 to 9. The final result is calculated as sum(dp[N]).
Implementation
Now, let’s implement all of this logic in Python code:
def count_stair_numbers(n):
# Constant for modular arithmetic
MOD = 1000000000
# Initialize DP table
dp = [[0] * 10 for _ in range(n + 1)]
# When the length is 1
for i in range(1, 10):
dp[1][i] = 1
# Fill the DP table
for i in range(2, n + 1):
dp[i][0] = dp[i - 1][1] % MOD
for j in range(1, 9):
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD
dp[i][9] = dp[i - 1][8] % MOD
# Calculate the result
result = sum(dp[n]) % MOD
return result
# User Input
n = int(input("Enter the value of N: "))
print(count_stair_numbers(n))
Conclusion
Today, through the “Counting Stair Numbers” problem, we have understood the basic concepts of dynamic programming and explored the process of solving problems using Python code. I hope this will enhance your algorithm problem-solving skills. Stay tuned for the next tutorial where we will cover another interesting algorithm problem!