c++ - 楼梯问题.. 为什么我的代码不适用于 n>21

Question

Simran 正在爬楼梯，一次N可以跳（跳）1 步、2 步或 3 步。你必须计算 Simran 有多少种可能的方式可以跑上楼梯。

输入是N，输出是可能方式的数量。

为什么这段代码不起作用N>21？

#include<bits/stdc++.h>
using namespace std;
long long fact(int n)
{
 return (n==0) || (n==1) ? 1 : n* fact(n-1);
}
int main()
{
    int n;
    cin>>n;
    long long count=0;
   
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            for(int k=0;k<=n;k++)
            {
                if((i*1+j*2+k*3)==n)
                {
                 count+=fact(i+j+k)/(fact(i)*fact(j)*fact(k));
                }
            }
        }
    }
    cout<<count;
    return 0;
}

标签： c++algorithmmath

Answer 1

如果 n 高达 21，那么fact(i+j+k)在最坏的情况下（i=21，j=0，k=0）可以一直到 21。21的阶乘在10^19的数量级，超出了long long的范围。所以会溢出。我建议你在这里使用动态编程。