数数通往第 n 级楼梯的路（顺序无关紧要）

Question

有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

Answer 1

假设你有 N 个楼梯。首先你必须了解 N 是奇数还是偶数。

如果是偶数，那么它将是 2 的倍数：N = 2*S，其中 S 是楼梯对的数量。

假设 N = 6 且 S = 3。您的第一个解是 {2,2,2}。比你可以用 1 + 1 楼梯改变前 2 个楼梯，你就得到了第二个解决方案 {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

Answer 2

上面的答案是正确的，但是如果你想知道DP在这个问题中是如何使用的，请看这个例子：

jumps =[1,2]

我们可以说

jump =1

，所以对于任何楼梯，路数始终等于

1

。

现在对于

jump=2

，对于楼梯

8

来说：没有任何方法将是（没有方法仅使用1到达8）+（没有方法使用1和2到达6，因为你可以从6 只增加了 2)。

所以代码将如下所示：

 for(int i=1; i<=n;i++)
     dp[i]=1;

for(int i=2;i<=n;i++)
    dp[i]=dp[i]+dp[i-2];

return dp[n];

Answer 3

由于顺序无关紧要，到达第 N 个位置的方法是： 1种方式： 1,1,1,1,1......1

剩余n/2种方式： 1,1,1,1,1......2 1,1,1,1,1.....2,2 。 。 。 1,2,2,2,2,2,2...2,2,2 或 2,2,2,2,2,2,2...2（取决于 n 是偶数还是奇数）。

我们可以有把握地说，到达第 N 个地方的方法是 n/2 +1

Answer 4

我们要做的是看看step是否是2的倍数，然后加1，否则不是。

        vector<int> dp(1+n, 0);
        dp[1] = 1;
        for(int i =2 ; i <=n; ++i){
            if(i&1){
                dp[i] = dp[i-1];
            }
            else{
                dp[i] = 1 + dp[i-1];
            }
        }
       return dp[n];