Problem Description<\/h2>\n
\n 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.\n <\/p>\n
Problem<\/h3>\n
\n Write a program to find the number of N-digit stair numbers given N.\n <\/p>\n
Input<\/h3>\n\n- Natural number N is given in the first line. (1 \u2264 N \u2264 100)<\/li>\n<\/ul>\n
Output<\/h3>\n\n- Print the number of N-digit stair numbers modulo 10007.<\/li>\n<\/ul>\n
Example Input<\/h3>\n3<\/pre>\nExample Output<\/h3>\n14<\/pre>\nExplanation<\/h3>\n
\n If N is 3, the 3-digit stair numbers are 123, 132, 210, 321, 234, 345, 456, 567, 678, 789, etc., totaling 14.\n <\/p>\n<\/section>\n\nSolution Process<\/h2>\n
\n To solve this problem, we can use the technique of Dynamic Programming.\n <\/p>\n
\n 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.\n <\/p>\n
Solution Approach<\/h3>\n\n- \nState Definition<\/strong>: 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).\n <\/li>\n
- \nInitial State Setup<\/strong>: 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.\n <\/li>\n
- \nState Transition<\/strong>: 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: <\/p>\n
\n dp[n][last] = dp[n-1][last-1] + dp[n-1][last+1]\n <\/pre>\n Here, last can take values from 1 to 8 (0 and 9 are limited to one side).\n <\/li>\n
- \nResult Calculation<\/strong>: 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.\n <\/li>\n<\/ol>\n<\/section>\n
\nJava Code Implementation<\/h2>\n\n import java.util.Scanner;\n\n public class StairNumber {\n public static void main(String[] args) {\n Scanner sc = new Scanner(System.in);\n int N = sc.nextInt();\n int MOD = 10007;\n\n \/\/ Initialize DP array\n int[][] dp = new int[N + 1][10];\n\n \/\/ Initialize 1-digit numbers\n for (int i = 1; i < 10; i++) {\n dp[1][i] = 1;\n }\n\n \/\/ Build DP table\n for (int n = 2; n <= N; n++) {\n for (int last = 0; last <= 9; last++) {\n if (last > 0) { \/\/ If last is not 0\n dp[n][last] += dp[n - 1][last - 1];\n }\n if (last < 9) { \/\/ If last is not 9\n dp[n][last] += dp[n - 1][last + 1];\n }\n dp[n][last] %= MOD; \/\/ MOD operation\n }\n }\n\n \/\/ Summarize results\n int result = 0;\n for (int last = 0; last <= 9; last++) {\n result = (result + dp[N][last]) % MOD;\n }\n\n \/\/ Output result\n System.out.println(result);\n sc.close();\n }\n }\n <\/pre>\n<\/section>\n\nExample<\/h2>\nInput<\/h3>\n3<\/pre>\nOutput<\/h3>\n14<\/pre>\nWhen running the above code, you can accurately calculate the number of 3-digit stair numbers.<\/p>\n<\/section>\n\nAdditional Notes<\/h2>\n
\n 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.\n <\/p>\n
\n Finally, dynamic programming problems can often be related to graph theory, so it’s essential to maintain this perspective when solving problems.\n <\/p>\n<\/section>\n
<\/main><\/p>\n
Output<\/h3>\n\n- Print the number of N-digit stair numbers modulo 10007.<\/li>\n<\/ul>\n
Example Input<\/h3>\n3<\/pre>\nExample Output<\/h3>\n14<\/pre>\nExplanation<\/h3>\n
\n If N is 3, the 3-digit stair numbers are 123, 132, 210, 321, 234, 345, 456, 567, 678, 789, etc., totaling 14.\n <\/p>\n<\/section>\n\nSolution Process<\/h2>\n
\n To solve this problem, we can use the technique of Dynamic Programming.\n <\/p>\n
\n 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.\n <\/p>\n
Solution Approach<\/h3>\n\n- \nState Definition<\/strong>: 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).\n <\/li>\n
- \nInitial State Setup<\/strong>: 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.\n <\/li>\n
- \nState Transition<\/strong>: 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: <\/p>\n
\n dp[n][last] = dp[n-1][last-1] + dp[n-1][last+1]\n <\/pre>\n Here, last can take values from 1 to 8 (0 and 9 are limited to one side).\n <\/li>\n
- \nResult Calculation<\/strong>: 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.\n <\/li>\n<\/ol>\n<\/section>\n
\nJava Code Implementation<\/h2>\n\n import java.util.Scanner;\n\n public class StairNumber {\n public static void main(String[] args) {\n Scanner sc = new Scanner(System.in);\n int N = sc.nextInt();\n int MOD = 10007;\n\n \/\/ Initialize DP array\n int[][] dp = new int[N + 1][10];\n\n \/\/ Initialize 1-digit numbers\n for (int i = 1; i < 10; i++) {\n dp[1][i] = 1;\n }\n\n \/\/ Build DP table\n for (int n = 2; n <= N; n++) {\n for (int last = 0; last <= 9; last++) {\n if (last > 0) { \/\/ If last is not 0\n dp[n][last] += dp[n - 1][last - 1];\n }\n if (last < 9) { \/\/ If last is not 9\n dp[n][last] += dp[n - 1][last + 1];\n }\n dp[n][last] %= MOD; \/\/ MOD operation\n }\n }\n\n \/\/ Summarize results\n int result = 0;\n for (int last = 0; last <= 9; last++) {\n result = (result + dp[N][last]) % MOD;\n }\n\n \/\/ Output result\n System.out.println(result);\n sc.close();\n }\n }\n <\/pre>\n<\/section>\n\nExample<\/h2>\nInput<\/h3>\n3<\/pre>\nOutput<\/h3>\n14<\/pre>\nWhen running the above code, you can accurately calculate the number of 3-digit stair numbers.<\/p>\n<\/section>\n\nAdditional Notes<\/h2>\n
\n 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.\n <\/p>\n
\n Finally, dynamic programming problems can often be related to graph theory, so it’s essential to maintain this perspective when solving problems.\n <\/p>\n<\/section>\n
<\/main><\/p>\n
Example Input<\/h3>\n3<\/pre>\nExample Output<\/h3>\n14<\/pre>\nExplanation<\/h3>\n
\n If N is 3, the 3-digit stair numbers are 123, 132, 210, 321, 234, 345, 456, 567, 678, 789, etc., totaling 14.\n <\/p>\n<\/section>\n\nSolution Process<\/h2>\n
\n To solve this problem, we can use the technique of Dynamic Programming.\n <\/p>\n
\n 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.\n <\/p>\n
Solution Approach<\/h3>\n\n- \nState Definition<\/strong>: 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).\n <\/li>\n
- \nInitial State Setup<\/strong>: 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.\n <\/li>\n
- \nState Transition<\/strong>: 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: <\/p>\n
\n dp[n][last] = dp[n-1][last-1] + dp[n-1][last+1]\n <\/pre>\n Here, last can take values from 1 to 8 (0 and 9 are limited to one side).\n <\/li>\n
- \nResult Calculation<\/strong>: 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.\n <\/li>\n<\/ol>\n<\/section>\n
\nJava Code Implementation<\/h2>\n\n import java.util.Scanner;\n\n public class StairNumber {\n public static void main(String[] args) {\n Scanner sc = new Scanner(System.in);\n int N = sc.nextInt();\n int MOD = 10007;\n\n \/\/ Initialize DP array\n int[][] dp = new int[N + 1][10];\n\n \/\/ Initialize 1-digit numbers\n for (int i = 1; i < 10; i++) {\n dp[1][i] = 1;\n }\n\n \/\/ Build DP table\n for (int n = 2; n <= N; n++) {\n for (int last = 0; last <= 9; last++) {\n if (last > 0) { \/\/ If last is not 0\n dp[n][last] += dp[n - 1][last - 1];\n }\n if (last < 9) { \/\/ If last is not 9\n dp[n][last] += dp[n - 1][last + 1];\n }\n dp[n][last] %= MOD; \/\/ MOD operation\n }\n }\n\n \/\/ Summarize results\n int result = 0;\n for (int last = 0; last <= 9; last++) {\n result = (result + dp[N][last]) % MOD;\n }\n\n \/\/ Output result\n System.out.println(result);\n sc.close();\n }\n }\n <\/pre>\n<\/section>\n\nExample<\/h2>\nInput<\/h3>\n3<\/pre>\nOutput<\/h3>\n14<\/pre>\nWhen running the above code, you can accurately calculate the number of 3-digit stair numbers.<\/p>\n<\/section>\n\nAdditional Notes<\/h2>\n
\n 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.\n <\/p>\n
\n Finally, dynamic programming problems can often be related to graph theory, so it’s essential to maintain this perspective when solving problems.\n <\/p>\n<\/section>\n
<\/main><\/p>\n
Example Output<\/h3>\n14<\/pre>\nExplanation<\/h3>\n
\n If N is 3, the 3-digit stair numbers are 123, 132, 210, 321, 234, 345, 456, 567, 678, 789, etc., totaling 14.\n <\/p>\n<\/section>\n\nSolution Process<\/h2>\n
\n To solve this problem, we can use the technique of Dynamic Programming.\n <\/p>\n
\n 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.\n <\/p>\n
Solution Approach<\/h3>\n\n- \nState Definition<\/strong>: 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).\n <\/li>\n
- \nInitial State Setup<\/strong>: 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.\n <\/li>\n
- \nState Transition<\/strong>: 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: <\/p>\n
\n dp[n][last] = dp[n-1][last-1] + dp[n-1][last+1]\n <\/pre>\n Here, last can take values from 1 to 8 (0 and 9 are limited to one side).\n <\/li>\n
- \nResult Calculation<\/strong>: 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.\n <\/li>\n<\/ol>\n<\/section>\n
\nJava Code Implementation<\/h2>\n\n import java.util.Scanner;\n\n public class StairNumber {\n public static void main(String[] args) {\n Scanner sc = new Scanner(System.in);\n int N = sc.nextInt();\n int MOD = 10007;\n\n \/\/ Initialize DP array\n int[][] dp = new int[N + 1][10];\n\n \/\/ Initialize 1-digit numbers\n for (int i = 1; i < 10; i++) {\n dp[1][i] = 1;\n }\n\n \/\/ Build DP table\n for (int n = 2; n <= N; n++) {\n for (int last = 0; last <= 9; last++) {\n if (last > 0) { \/\/ If last is not 0\n dp[n][last] += dp[n - 1][last - 1];\n }\n if (last < 9) { \/\/ If last is not 9\n dp[n][last] += dp[n - 1][last + 1];\n }\n dp[n][last] %= MOD; \/\/ MOD operation\n }\n }\n\n \/\/ Summarize results\n int result = 0;\n for (int last = 0; last <= 9; last++) {\n result = (result + dp[N][last]) % MOD;\n }\n\n \/\/ Output result\n System.out.println(result);\n sc.close();\n }\n }\n <\/pre>\n<\/section>\n\nExample<\/h2>\nInput<\/h3>\n3<\/pre>\nOutput<\/h3>\n14<\/pre>\nWhen running the above code, you can accurately calculate the number of 3-digit stair numbers.<\/p>\n<\/section>\n\nAdditional Notes<\/h2>\n
\n 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.\n <\/p>\n
\n Finally, dynamic programming problems can often be related to graph theory, so it’s essential to maintain this perspective when solving problems.\n <\/p>\n<\/section>\n
<\/main><\/p>\n
Explanation<\/h3>\n
\n If N is 3, the 3-digit stair numbers are 123, 132, 210, 321, 234, 345, 456, 567, 678, 789, etc., totaling 14.\n <\/p>\n<\/section>\n \n To solve this problem, we can use the technique of Dynamic Programming.\n <\/p>\n \n 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.\n <\/p>\n Here, last can take values from 1 to 8 (0 and 9 are limited to one side).\n <\/li>\n When running the above code, you can accurately calculate the number of 3-digit stair numbers.<\/p>\n<\/section>\n \n 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.\n <\/p>\n \n Finally, dynamic programming problems can often be related to graph theory, so it’s essential to maintain this perspective when solving problems.\n <\/p>\n<\/section>\n <\/main><\/p>\nSolution Process<\/h2>\n
Solution Approach<\/h3>\n
\n
\n dp[n][last] = dp[n-1][last-1] + dp[n-1][last+1]\n <\/pre>\n
Java Code Implementation<\/h2>\n
\n import java.util.Scanner;\n\n public class StairNumber {\n public static void main(String[] args) {\n Scanner sc = new Scanner(System.in);\n int N = sc.nextInt();\n int MOD = 10007;\n\n \/\/ Initialize DP array\n int[][] dp = new int[N + 1][10];\n\n \/\/ Initialize 1-digit numbers\n for (int i = 1; i < 10; i++) {\n dp[1][i] = 1;\n }\n\n \/\/ Build DP table\n for (int n = 2; n <= N; n++) {\n for (int last = 0; last <= 9; last++) {\n if (last > 0) { \/\/ If last is not 0\n dp[n][last] += dp[n - 1][last - 1];\n }\n if (last < 9) { \/\/ If last is not 9\n dp[n][last] += dp[n - 1][last + 1];\n }\n dp[n][last] %= MOD; \/\/ MOD operation\n }\n }\n\n \/\/ Summarize results\n int result = 0;\n for (int last = 0; last <= 9; last++) {\n result = (result + dp[N][last]) % MOD;\n }\n\n \/\/ Output result\n System.out.println(result);\n sc.close();\n }\n }\n <\/pre>\n<\/section>\nExample<\/h2>\n
Input<\/h3>\n
3<\/pre>\n
Output<\/h3>\n
14<\/pre>\n
Additional Notes<\/h2>\n