> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/total-number-of-different-staircase-that-can-made-from-n-boxes.md).

# Total number of different staircase that can made from N boxes

Given N boxes each of unit dimension i.e. (1×1 ![meter^2](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-03feead287139ee993eed8c440a0d6df_l3.svg)). The task is to find the total number of different staircases that can be made from those boxes with the following rules:

* Staircase must be in strictly descending order.
* Each staircase contains at least two steps. (Total steps is equal to the breadth of the staircase.)

**Examples**:

> **Input** : N = 5\
> **Output** : 2\
> The two staircase are following :\
> ![](https://media.geeksforgeeks.org/wp-content/uploads/SC-copy-300x267.jpg)\ <br>
>
> **Input** : N = 6\
> **Output** : 3\
> The three staircase are following :\
> ![](https://media.geeksforgeeks.org/wp-content/uploads/SC-1-300x178.jpg)

If we consider total steps = 2, we can observe the fact that the number of staircase is incremented by 1 if N is incremented by 2. We can illustrate the above thing from the following image :

![](https://media.geeksforgeeks.org/wp-content/uploads/Untitled-drawing-35.jpg)

Now, if total steps is greater than 2 (assume, total steps = K) then we can take this thing as first create a base (base requires boxes equal to the total steps) for staircase and put another staircase on it of steps size K and K – 1 having boxes N – K. (because K boxes already used to create base). Thus, we can solve this problem using bottom-up dynamic programming.

```java
public class Solution {
    public int countStaircases(int N) {
        // dp[i][j] -> number of stair cases possible with i bricks which has j
        // width(steps)
        int[][] dp = new int[N][N];
        // Base case
        dp[3][2] = dp[4][2] = 1;
        for (int i = 5; i <= N; i++) {
            for (int j = 2; j <= i; j++) {
                // When step is equal to 2
                if (j == 2)
                    dp[i][j] = dp[i - j][j] + 1;
                // When step is greater than 2
                else
                    dp[i][j] = dp[i - j][j] + dp[i - j][j - 1];
            }
        }

        int answer = 0;
        for (int i = 1; i <= N; i++)
            answer = answer + dp[N][i];

        return answer;
    }
}
```