Count ways to n'th stair(order does not matter)

Question

There are N stairs, and a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top (order does not matter). Note: Order does not matter means for n=4 {1 2 1},{2 1 1},{1 1 2} are considered same.

https://practice.geeksforgeeks.org/problems/count-ways-to-nth-stairorder-does-not-matter/0

So I have been trying to solve this question and the problem I am facing is that I don't understand how do we solve questions like these where the order does not matter? I was able to solve the question when order mattered but I am not able to develop the logic to solve this.

This is the code I wrote for when order mattered

long int countWaysToStair(long int N)
{
    if(N == 1 || N == 2)
    return N;

    long int dp[N+1];

    dp[0] = 1;
    dp[1] = 1;

    dp[2] = 2;

    for(int i=3;i<=N;i++)
    {
      dp[i] = dp[i-1] + dp[i-2];
    } 
    return dp[N];
}

Input: 4 Expected Output: 3 My output: 5

Answer 1

Consider that you have N stairs. First of all you have to understand if N is odd or even.

If is even than it will be a multiple of 2: N = 2*S, where S is the number of pair of stairs.

Suppose N = 6 and S = 3. Your first solution is {2,2,2}. than you can change the first 2 stairs with 1 + 1 stairs and you have your second solution {1, 1, 2 ,2}. Since order doesn't matter let's proceed with the next pair and we have our third solution {1, 1, 1, 1, 2} and then the fourth {1, 1, 1, 1, 1, 1}

Given N = 2*S the number of possible solutions are S + 1.

Now suppose N is odd and N = 2S + 1. Let N = 7 and S = 3. Our solutions are {2,2,2,1}, {1,1,2,2,1}, {1,1,1,1,2,1} and {1,1,1,1,1,1,1}. Again, the number of solutions is given by S+1

Now your algorithm is pretty simple:

return N/2 + 1