POJ 1775 dfs 또는 dp

//11352654	c00h00g	1775	Accepted	384K	500MS	G++	635B	2013-03-15 17:31:41
//       ，        
#include<stdio.h>
#include<string.h>

int fib[10]={1,1,2,6,24,120,720,5040,40320,362880};
int n;
int vis[10];

int dfs(int i,int data){
    if(data==n) return 1;
    if(data>n) return 0;
    for(int j=i;j<10;j++){
        if(!vis[j]){
            vis[j]=1;
            if(dfs(j+1,data+fib[j])) return 1;//        ，       
            vis[j]=0;
        }
    }
    return 0;
}

int main(){
    while(scanf("%d",&n)&&n>=0){
        if(n==0) { printf("NO
");continue;}       
        memset(vis,0,sizeof(vis));        
        if(dfs(0,0)) printf("YES
");
        else printf("NO
");
    }
    return 0;
}

//11352748	c00h00g	1775	Accepted	4296K	110MS	G++	664B	2013-03-15 18:06:48
//dp  ，            
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define INF 0x7fffffff
int fib[10]={1,1,2,6,24,120,720,5040,40320,362880};
int n;
int dp[1000005]; 

int main(){
    for(int i=1;i<1000005;i++)
        dp[i]=-INF;
    dp[0]=0;
    for(int i=0;i<10;i++)//    
        for(int V=1000004;V>=0;V--){
            if(V-fib[i]>=0&&dp[V-fib[i]]!=-INF)
                dp[V]=max(dp[V],dp[V-fib[i]]+fib[i]);
            }
    while(scanf("%d",&n)&&n>=0){
        if(n==0) { printf("NO
");continue;}             
        //        
        if(dp[n]>0) printf("YES
");
        else printf("NO
");
    }
    return 0;
}