Author: root

Hello, today we will solve one of the algorithm problems useful for JavaScript coding test preparation, called “Counting Stair Numbers”. This problem can be approached interestingly using Dynamic Programming and combinatorial methods. In this article, I will provide a detailed explanation including the problem description, the solution process, and optimization strategies.

Problem Description

A stair number refers to a number of n digits where the difference between two adjacent digits is 1. For example, numbers like 123 and 321 are stair numbers since the difference between adjacent digits is 1. Write a program to find the n-digit stair numbers for the given n.

Input

An integer n (1 ≤ n ≤ 1000)

Output

Output the number of n-digit stair numbers modulo 1,000,000,000.

Problem Solving Strategy

To solve this problem, we can use a dynamic programming approach. Stair numbers can be defined by the following state:

• dp[i][j]: the number of i-digit stair numbers that end with j

The rules for forming stair numbers can be established as follows:

• When j is 0 (no number can start with 0): dp[i][0] = dp[i-1][1]
• When j is 9: dp[i][9] = dp[i-1][8]
• In other cases: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

Initialization of the Dynamic Programming Table

Now let’s initialize the dp table. For 1-digit numbers, since digits can range from 0 to 9, we initialize dp[1][0] to dp[1][9] to 1 respectively.

Solution Code

function countStairNumbers(n) {
    const MOD = 1000000000;
    const dp = Array.from({ length: n + 1 }, () => Array(10).fill(0));

    // Initialize 1-digit numbers
    for (let j = 0; j < 10; j++) {
        dp[1][j] = 1;
    }

    // Fill the dp table
    for (let i = 2; i <= n; i++) {
        for (let j = 0; j < 10; j++) {
            if (j > 0) dp[i][j] += dp[i - 1][j - 1]; // Move from j-1
            if (j < 9) dp[i][j] += dp[i - 1][j + 1]; // Move from j+1
            dp[i][j] %= MOD; // modulo operation
        }
    }

    // Sum of all n-digit stair numbers
    let result = 0;
    for (let j = 0; j < 10; j++) {
        result += dp[n][j];
    }

    return result % MOD;
}

// Example of function call
console.log(countStairNumbers(3)); // 24

Time Complexity

The time complexity of the above code is O(n), and the space complexity is O(n). Since the result is derived through combinations of each digit, it efficiently uses time and space as n increases.

Optimization Strategies

To reduce memory usage in the currently implemented code, we can change the dp array from two-dimensional to one-dimensional. Since only the previous dp state is needed for each i, this can be utilized for optimization.

function countStairNumbersOptimized(n) {
    const MOD = 1000000000;
    const dp = Array(10).fill(0);
    const temp = Array(10).fill(0);

    // Initialize 1-digit numbers
    for (let j = 0; j < 10; j++) {
        dp[j] = 1;
    }

    for (let i = 2; i <= n; i++) {
        for (let j = 0; j < 10; j++) {
            temp[j] = 0;
            if (j > 0) temp[j] += dp[j - 1]; // Move from j-1
            if (j < 9) temp[j] += dp[j + 1]; // Move from j+1
            temp[j] %= MOD; // modulo operation
        }
        for (let j = 0; j < 10; j++) {
            dp[j] = temp[j]; // Update for the next step
        }
    }

    // Sum of all n-digit stair numbers
    let result = 0;
    for (let j = 0; j < 10; j++) {
        result += dp[j];
    }

    return result % MOD;
}

Conclusion

In this article, we learned how to solve the “Counting Stair Numbers” problem using dynamic programming in JavaScript. I provided a detailed explanation of initialization, constructing the dp table, and the optimization process, as well as methods to enhance the efficiency of the algorithm through various techniques. When solving algorithm problems, always consider multiple approaches and explore ways to optimize them. Thank you!

Coding tests are taken by many developers, and they are assessed through various algorithm problems. In this article, we will take a closer look at the algorithm problem-solving process through the ‘pathfinding’ problem. This problem is suitable for using graph traversal techniques such as DFS (Depth-First Search) or BFS (Breadth-First Search).

Problem Description

You need to find a path from the starting point to the destination point in a given 2D grid. Each cell of the grid indicates whether it can be moved to or not, and the following are the problem conditions:

• The grid has dimensions N x M.
• Each cell is marked with 0 or 1, where 0 indicates a traversable path and 1 indicates a blocked path.
• The starting point is at (0, 0) and the destination point is at (N-1, M-1).
• You can move up, down, left, or right.

Example Input

    4 4
    0 0 1 0
    0 1 0 0
    0 1 1 0
    0 0 0 0
    

Example Output

    Yes
    

Problem Solving Process

The algorithm we will use to solve this problem is BFS. BFS is advantageous for finding the shortest path as it explores each node in order. We will solve the problem through the following steps:

1. Create the grid space

Convert the received grid information into an array. This will facilitate access to and movement through each cell.

2. Initialize BFS

Add the starting point (0, 0) to the queue. Additionally, we use an extra array to track visited nodes.

3. Perform BFS search

Repeat the following while the queue is not empty:

• Dequeue a node to check the current position.
• Check if the current position is the destination point (N-1, M-1). If so, output ‘Yes’ and terminate the search.
• For all cells that can be moved to up, down, left, or right, do the following:
• Check the boundary conditions and whether it has been visited.
• If the cell’s value is 0 and it has not been visited, add it to the queue and mark it as visited.

If the search completes and the destination point has not been reached, output ‘No’.

4. Code Implementation

    function canReachDestination(grid) {
        const N = grid.length;
        const M = grid[0].length;
        const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        const queue = [[0, 0]];
        const visited = Array.from({length: N}, () => Array(M).fill(false));

        visited[0][0] = true;

        while (queue.length > 0) {
            const [x, y] = queue.shift();

            // Check the destination point
            if (x === N - 1 && y === M - 1) {
                return "Yes";
            }

            for (const [dx, dy] of directions) {
                const nx = x + dx;
                const ny = y + dy;

                // Check boundary conditions and whether visited
                if (nx >= 0 && ny >= 0 && nx < N && ny < M && 
                    !visited[nx][ny] && grid[nx][ny] === 0) {
                    visited[nx][ny] = true;
                    queue.push([nx, ny]);
                }
            }
        }
        return "No";
    }

    const grid = [
        [0, 0, 1, 0],
        [0, 1, 0, 0],
        [0, 1, 1, 0],
        [0, 0, 0, 0]
    ];
    console.log(canReachDestination(grid)); // Result: "Yes"
    

Conclusion

Through this problem, we have solved a pathfinding problem using the BFS algorithm. In actual coding tests, you will often encounter such problems, so it is important to practice various algorithms to develop problem-solving skills for diverse challenges. In the next lesson, we will address different types of algorithm problems. Thank you!