C++ Coding Test Course, Counting Stairways

1. Problem Description

The number of stairs refers to the combinations of ways to climb stairs by choosing either to go up or down. The given problem is as follows.

Given an integer N, write a program to calculate the number of ways to climb N stairs.

However, you can climb either one or two stairs at a time, and the last stair number must end with a digit from 1 to 9.

For example, the ways to climb 4 stairs are as follows:

• 1111 (1+1+1+1)
• 112 (1+1+2)
• 121 (1+2+1)
• 211 (2+1+1)
• 22 (2+2)

Considering the above cases, you need to write code to correctly calculate the number of stairs.

2. Problem Analysis

Let us analyze some important points to solve the problem.

• State Definition: The Nth stair is composed differently depending on the state of the previous stairs. For example, look at the counts for N=1 and N=2.
• Recurrence Relation: The way to climb N stairs is the sum of the number of ways to climb 1 stair from N-1 stairs and the number of ways to climb 2 stairs from N-2 stairs. The last stair number must be one of the digits from 1 to 9.
• Result: The number of ways to climb N stairs is the sum of all the counts of each case.

3. Deriving the Recurrence Relation

The general recurrence relation can be expressed as follows:

dp[i][j] = dp[i-1][j-1] + dp[i-2][j]
            

Here, dp[i][j] represents the number of ways ending with j at the i-th stair. The initial conditions can be set as dp[1][1] = 1, dp[1][2] = 1 … dp[1][9] = 1. Based on this, we can write the following code.

4. Code Design

Now let’s write code in C++. This code takes the given N as an input and prints the corresponding number of ways to climb stairs.

#include <iostream>

using namespace std;

const int MOD = 1000000000; // MOD setting for large number processing
int dp[100][10]; // dp table

void init() {
    for (int i = 1; i <= 9; i++) {
        dp[1][i] = 1; // Number of ways to climb one stair
    }
  
    for (int i = 2; i <= 100; i++) {
        for (int j = 0; j <= 9; j++) {
            // Case ending with 0 (j == 0)
            if (j == 0) {
                dp[i][0] = dp[i - 1][1] % MOD; 
            }
            // Case ending with 9 (j == 9)
            else if (j == 9) {
                dp[i][9] = dp[i - 1][8] % MOD; 
            }
            // Other cases
            else {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
            }
        }
    }
}

int main() {
    int N;
    cin >> N; // Input number of stairs
    init(); // Initialize dp table

    long long total = 0;
    for (int i = 0; i <= 9; i++) {
        total = (total + dp[N][i]) % MOD; // Calculate total number of cases
    }

    cout << total << endl; // Output result
    return 0;
}
            

5. Code Explanation

The above code is written in a dynamic programming style to calculate the number of stairs.

• Input Handling: It takes N as input from the user to calculate the number of stairs.
• Table Initialization: The first row of the dp table is initialized to set each ending digit to 1.
• Applying the Recurrence Relation: It calculates the possible counts for each number of stairs and saves the values divided by MOD.
• Result Calculation: It sums all counts from 1 to 9 and outputs the final result.

6. Complexity Analysis

The time complexity of this algorithm is O(N), which takes linear time for the given N. The space complexity also has a size of O(N). This ensures efficiency in both memory and time.

7. Conclusion

The stair number problem is suitable for learning the basic concepts of dynamic programming. Performing this problem greatly aids in understanding recursive thinking and the concept of memoization. By solving this problem through the C++ Programming Language, you can further strengthen your algorithm problem-solving skills.

Hope this course helps you in preparing for the C++ coding test! Learn it, and try solving more problems!