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.<\/p>\n
A stair number is defined by the following rules:<\/p>\n
Given a natural number The first line contains the number of digits in the stair number The first line should output the number of N-digit stair numbers modulo 1,000,000,000.<\/p>\n 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.<\/p>\n To find N-digit stair numbers, we define a DP array. We use The stair numbers of length 1 are from 1 to 9. Therefore, we set To construct stair numbers of length 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 Now, let’s implement all of this logic in Python code:<\/p>\n 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!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"N<\/code>, 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.<\/p>\nInput Format<\/h2>\n
N<\/code> (1 \u2264 N \u2264 100).<\/p>\nOutput Format<\/h2>\n
Example Input<\/h3>\n
\n2\n<\/pre>\n
Example Output<\/h3>\n
\n15\n<\/pre>\n
Problem Solving Strategy<\/h2>\n
Step 1: State Definition<\/h3>\n
dp[n][k]<\/code> to represent the number of stair numbers of length n<\/code> whose last digit is k<\/code>. Here, n<\/code> is the number of digits, and k<\/code> is the last digit (0 to 9).<\/p>\nStep 2: Initial Condition Setting<\/h3>\n
dp[1][0] = 0<\/code> (0 cannot be the first digit), and dp[1][1] = dp[1][2] = ... = dp[1][9] = 1<\/code>.<\/p>\nStep 3: Deriving the Recursion Formula<\/h3>\n
n<\/code>, we add one digit to stair numbers of length n-1<\/code>. If the last digit is 0<\/code>, it can lead to 1<\/code>, and if the last digit is 9<\/code>, it can lead to 8<\/code>. Therefore, we get the following recursion formulas:<\/p>\n\ndp[n][0] = dp[n-1][1]\ndp[n][k] = dp[n-1][k-1] + dp[n-1][k+1] (1 <= k <= 8)\ndp[n][9] = dp[n-1][8]\n<\/pre>\n
Step 4: Calculating the Final Result<\/h3>\n
sum(dp[N])<\/code>.<\/p>\nImplementation<\/h2>\n
def count_stair_numbers(n):\n # Constant for modular arithmetic\n MOD = 1000000000\n\n # Initialize DP table\n dp = [[0] * 10 for _ in range(n + 1)]\n\n # When the length is 1\n for i in range(1, 10):\n dp[1][i] = 1\n\n # Fill the DP table\n for i in range(2, n + 1):\n dp[i][0] = dp[i - 1][1] % MOD\n for j in range(1, 9):\n dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD\n dp[i][9] = dp[i - 1][8] % MOD\n\n # Calculate the result\n result = sum(dp[n]) % MOD\n return result\n\n# User Input\nn = int(input(\"Enter the value of N: \"))\nprint(count_stair_numbers(n))\n<\/code><\/pre>\nConclusion<\/h2>\n