Let’s improve our problem-solving skills in actual exams by solving various algorithm problems in preparation for the coding test.
Problem Description
Stair numbers follow the following rules. They are n-digit numbers, and each digit must increase in ascending order. That is, the difference between two adjacent digits must be exactly 1. For example, 123, 234, and 345 are all stair numbers.
Problem
Write a program to find the number of N-digit stair numbers given N.
Input
- Natural number N is given in the first line. (1 ≤ N ≤ 100)
Output
- Print the number of N-digit stair numbers modulo 10007.
Example Input
3
Example Output
14
Explanation
If N is 3, the 3-digit stair numbers are 123, 132, 210, 321, 234, 345, 456, 567, 678, 789, etc., totaling 14.
Solution Process
To solve this problem, we can use the technique of Dynamic Programming.
Stair numbers can be thought of as combinations of N-digit numbers based on the previous N-1 digit numbers. The last digit of the N-digit number is determined by the last digit of the N-1 digit numbers, so we simply update the DP array considering this.
Solution Approach
- State Definition: Define dp[n][last] as the number of n-digit stair numbers where the last digit is last. n refers to the number of digits, and last refers to the last digit (0-9).
- Initial State Setup: For 1-digit numbers (i.e., when N=1), each digit (1-9) has exactly 1 case. Thus, dp[1][1] to dp[1][9] will be 1, and dp[1][0] will be 0.
-
State Transition: n-digit numbers are created from n-1 digit numbers. When the last digit is last, the last digit can either be last-1 or last+1. This can be expressed as follows:
dp[n][last] = dp[n-1][last-1] + dp[n-1][last+1]Here, last can take values from 1 to 8 (0 and 9 are limited to one side).
- Result Calculation: The number of N-digit numbers is the sum of dp[N][0] + dp[N][1] + … + dp[N][9]. However, since the problem requires the result modulo 10007, this operation must be performed during the calculation.
Java Code Implementation
import java.util.Scanner;
public class StairNumber {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int MOD = 10007;
// Initialize DP array
int[][] dp = new int[N + 1][10];
// Initialize 1-digit numbers
for (int i = 1; i < 10; i++) {
dp[1][i] = 1;
}
// Build DP table
for (int n = 2; n <= N; n++) {
for (int last = 0; last <= 9; last++) {
if (last > 0) { // If last is not 0
dp[n][last] += dp[n - 1][last - 1];
}
if (last < 9) { // If last is not 9
dp[n][last] += dp[n - 1][last + 1];
}
dp[n][last] %= MOD; // MOD operation
}
}
// Summarize results
int result = 0;
for (int last = 0; last <= 9; last++) {
result = (result + dp[N][last]) % MOD;
}
// Output result
System.out.println(result);
sc.close();
}
}
Example
Input
3
Output
14
When running the above code, you can accurately calculate the number of 3-digit stair numbers.
Additional Notes
After solving the problem, it is important to verify the algorithm’s accuracy with various test cases. Additionally, optimizing the code or approaching the algorithm in different ways and comparing the results is also a good practice.
Finally, dynamic programming problems can often be related to graph theory, so it’s essential to maintain this perspective when solving problems.