---

方法一：打表，能减就减

数据范围n≤1,000,000，小于10！ 因此考虑打表。

思路：

在fact[0~9]依次存入阶乘值，从大到小与n比较，小于n则从n中减去该值。当n==0时可提前跳出循环

最后判断条件：若跳出循环时i=-1&&n!=0（若没有n!=0则过不了4的样例），则输出NO

否则输出YES

#include <iostream>
#include <cstdio>

using namespace std;

int fact[10];
int n;
void Getfact()
{
    fact[0]=1;
    for(int i=1;i<10;i++)
        fact[i]=fact[i-1]*i;
    return ;
}



int main()
{
    Getfact();
    while(cin>>n)
    {
        if(n==0)
        {
            cout<<"NO"<<endl;
            continue;
        }
        int i;
        for( i=9;i>=0;i--)
        {
            if(n==0) break;

            if(n>=fact[i])
                n-=fact[i];
        }

        if(i==-1&&n!=0)
            puts("NO");

        else
            puts("YES");

    }
    return 0;

}

 

方法二：DFS

设置N=1e6,使用循环判断最大的maxIndex值，并将小于maxIndex的i的阶乘存储fact中

深搜思想：从小到大加入结点，每次先将当前结点加入。

(1)当sum小于n时，则将当前结点加入，并向下...