c++ - 计算通往第n个楼梯的方式(顺序无关紧要)

有N个楼梯，一个站在底部的人想要到达顶部。此人可以一次爬1阶或2阶。数一数，人可以达到顶峰(顺序无所谓)。
注意:顺序无关紧要，因为n = 4 {1 2 1}，{2 1 1}，{1 1 2}被认为是相同的。
https://practice.geeksforgeeks.org/problems/count-ways-to-nth-stairorder-does-not-matter/0
所以我一直在尝试解决这个问题，而我面临的问题是我不了解在顺序无关紧要的情况下如何解决此类问题？当顺序很重要时，我能够解决问题，但是我无法开发逻辑来解决该问题。
这是我在订购时很重视的代码

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];
}

输入:
4
预期产量:
3
我的输出:
5

最佳答案

考虑您有N个楼梯。首先，您必须了解N是否为奇数或偶数。
如果为，则为2的倍数:N = 2 * S，其中S为楼梯对数。
假设N = 6且S =3。您的第一个解决方案是{2,2,2}。那么您可以将前2个楼梯更改为1 + 1个楼梯，然后有了第二个解决方案{1，1，2，2}。
由于顺序无关紧要，所以让我们继续下一对，然后我们得到第三个解{1，1，1，1，2}，然后是第四个解{1，1，1，1，1，1}
给定N = 2 * S，可能的解数为S + 1。
现在假设N为奇数，并且N = 2S + 1。
令N = 7且S =3。我们的解为{2,2,2,1}，{1,1,2,2,1}，{1,1,1,1,2,1}和{1 ，1,1,1,1,1,1}。同样，解决方案的数量由S + 1给出
现在，您的算法非常简单:

return N/2 + 1